Ga sengaja ketemu soal di papan tulis kampus :D
Buktikan, untuk setiap n anggota bilangan asli (n ∈ {1, 2, 3, …}) ada kelipatan dari n yang setiap digitnya hanya terdiri dari angka 0 atau 1 !
(mis. 10101 adalah kelipatan 3, 1111110 adalah kelipatan 7, 1000 adalah kelipatan 8, dll)
Keliatannya bingung ya gimana cara membuktikannya? Ternyata, tidak terlalu sulit! Thanks buat temen saya yang dewa matematika, saya bisa cukup ngerti dengan ide pembuktiannya :D
Pembuktian
Misalnya kita definisikan suatu himpunan A yang anggotanya adalah bilangan bulat yang hanya terdiri dari angka 1, sehingga
lalu, kita definisikan lagi sebuah himpunan B yang anggotanya adalah hasil modulo dari setiap anggota himpunan A dengan n (sebuah bilangan asli, sesuai dengan definisi dari soal), sehingga
Oleh karena hanya ada n buah nilai yang mungkin untuk B, maka diantara n+1 buah anggota B pasti ada yang sama. Dengan kata lain ada p dan q dengan p < q < n+1, p dan q bilangan asli sehingga Bp = Bq.
\[B_p = B_q\]
\[A_p \mod n = A_q \mod n\]
berdasarkan sifat dari modulo, berlaku
\[(A_p - A_q) \mod n = B_p - B_q = 0\]
karena $(A_p - A_q) \mod n = 0 \displaystyle$ maka $A_p - A_q \displaystyle $ adalah kelipatan dari n.
Dan karena setiap anggota A merupakan bilangan yang hanya terdiri dari angka 1, maka $A_p - A_q \displaystyle$ merupakan bilangan yang hanya terdiri dari angka 0 dan 1. (terbukti)
Buktikan, untuk setiap n anggota bilangan asli (n ∈ {1, 2, 3, …}) ada kelipatan dari n yang setiap digitnya hanya terdiri dari angka 0 atau 1 !
(mis. 10101 adalah kelipatan 3, 1111110 adalah kelipatan 7, 1000 adalah kelipatan 8, dll)
Keliatannya bingung ya gimana cara membuktikannya? Ternyata, tidak terlalu sulit! Thanks buat temen saya yang dewa matematika, saya bisa cukup ngerti dengan ide pembuktiannya :D
Pembuktian
Misalnya kita definisikan suatu himpunan A yang anggotanya adalah bilangan bulat yang hanya terdiri dari angka 1, sehingga
\[ A = \{1, 11, 111, 1111, ...\} \]
lalu, kita definisikan lagi sebuah himpunan B yang anggotanya adalah hasil modulo dari setiap anggota himpunan A dengan n (sebuah bilangan asli, sesuai dengan definisi dari soal), sehingga
\[ B = \{1 \mod n, 11 \mod n, 111 \mod n, 1111 \mod n, ...\} \]
perhatikan bahwa nilai dari $B_i = A_i \mod n$ itu selalu berada dalam range [0..n -1], sehingga hanya terdapat n buah nilai yang mungkin untuk Bi.Oleh karena hanya ada n buah nilai yang mungkin untuk B, maka diantara n+1 buah anggota B pasti ada yang sama. Dengan kata lain ada p dan q dengan p < q < n+1, p dan q bilangan asli sehingga Bp = Bq.
\[B_p = B_q\]
\[A_p \mod n = A_q \mod n\]
berdasarkan sifat dari modulo, berlaku
\[(A_p - A_q) \mod n = B_p - B_q = 0\]
karena $(A_p - A_q) \mod n = 0 \displaystyle$ maka $A_p - A_q \displaystyle $ adalah kelipatan dari n.
Dan karena setiap anggota A merupakan bilangan yang hanya terdiri dari angka 1, maka $A_p - A_q \displaystyle$ merupakan bilangan yang hanya terdiri dari angka 0 dan 1. (terbukti)
