Kelipatan dengan angka 1 dan 0 « Art of Mathematics

29 April 2008

Kelipatan dengan angka 1 dan 0

Diarsipkan di bawah: Teori Bilangan — Tag:angka, bukti, kelipatan, olympiad, Pigeonhole Principle, prinsip rumah burung, problem book, relatif prima, Teori Bilangan, ussr — Johan @ 21:12

[USSR Olympiad Problem Book] Buktikan bahwa setiap bilangan asli $N$ memiliki kelipatan yang hanya terdiri dari angka 1 dan 0. Jika $N$ relatif prima dengan 10, buktikan bahwa $N$ memiliki kelipatan yang hanya terdiri dari angka 1.

Solusi
Di antara bilangan-bilangan

$\displaystyle\left\{1,11,111,\ldots,\underbrace{111\ldots1}_{n}\right\}$ ,

pasti terdapat dua bilangan yang sisanya sama ketika dibagi $N$ . Misalkan bilangan itu $k$ dan $l$ . Maka $k-l$ habis dibagi $N$ . Tetapi $k-l$ berbentuk $111\ldots1000\ldots0$ , beberapa angka satu diikuti beberapa angka 0, sehingga pernyataan pertama terbukti. Jika $N$ relatif prima dengan $10$ , maka faktor-faktor 10 pada $k-l$ dapat diabaikan, sehingga $111\ldots1$ habis dibagi $N$ .