Кратные числа

[wpoms.]

Пусть `n` — натуральное число. Покажите, что существует число, кратное `n`, состоящее только из цифр `0` и `1`.

@темы: Теория чисел

Comments

[Trotill]

Пусть n не делит 2 и 5.
Тогда такое число: 10^(n-1) + 10^2(n-1)+...(n слагаемых) по малой теореме Ферма.

Пусть n делит 2^a*5^b.
Делим его на 2^a*5^b, поступаем аналогично 1, но в качестве основания можно брать не 10, а 10^c > 2^a*5^b. Тогда полученное число будет делить и n, и 2^a*5^b.

Верное решение?

[Trotil]

Интересно, если не знать малую теорему Ферма (и не выводить её), то решить можно другим способом?

[Гость]

Рассмотрим число, состоящее из n единиц. Если оно делится на n, то решение найдено. В противном случае рассмотрим последовательность, состоящую из чисел, образованных n, n+1, n+2, ... единицами. В этой последовательности найдутся два числа, дающие одинаковые остатки при делении на n. Модуль их разности делится на n и его десятичная запись состоит из 1 и 0.