Докажите, что для любого натурального N, взаимно простого с 10, существует репьюнит (число из единиц), кратный N, например, 111 делится на 3, а 111111 делится на 7 и 13

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи можно воспользоваться теоремой Эйлера.

Пусть a и n - числа, взаимно простые между собой. Тогда по теореме Эйлера существует натуральное число k, такое что a^φ(n) ≡ 1 (mod n), где φ(n) - функция Эйлера, равная количеству натуральных чисел, меньших и взаимно простых с n.

В данном случае нам дано, что N взаимно просто с 10, поэтому нам нужно найти k, такое что 10^k ≡ 1 (mod N).

Рассмотрим число 111...1 (k единиц). Если мы поделим это число на 10^k - 1, то получим остаток в виде последовательности из k единиц. То есть 111...1 (k единиц) ≡ 0 (mod 10^k - 1).

Таким образом, если мы возьмем достаточно много единиц и поделим их на 10^k - 1, получим число, которое будет кратно N, так как N взаимно просто с 10.

Например, пусть N = 13. Тогда 10^3 ≡ 1 (mod 13), следовательно 111 делится на 13.

Аналогично для N = 7 имеем 10^6 ≡ 1 (mod 7), поэтому 111111 делится на 7.

Таким образом, для любого натурального числа N, взаимно простого с 10, существует число из единиц, кратное N.