Делится ли число: 1111...111 - 81 раз, на 81?

Рассмотрим число вида
$N = 111\ldots111$ (единица повторяется 81 раз). Нужно понять, делится ли $N$ на 81.

1) Что значит делимость на 81

Так как $81 = 9 \cdot 9$, то делимость на 81 эквивалентна одновременной делимости на 9 и на 81 (понятно), но удобнее проверять именно на 9 и на 81 через остатки по модулю 81.

Сначала быстро проверим на 9:

• Сумма цифр числа $N$ равна $81$, потому что там 81 единица.

• $81$ делится на 9, значит $N$ делится на 9.

Но этого недостаточно: делимость на 9 не гарантирует делимость на 81.

2) Запишем число как геометрическую сумму

Число из 81 единицы можно записать так:

Нужно проверить, делится ли $N$ на 81, то есть равен ли $N \equiv 0 \pmod{81}$.

Эквивалентно проверить:

Это означает, что

потому что умножаем обе части на 9: если $N$ кратно 81, то $9N$ кратно $729=9\cdot81$, а $9N = 10^{81}-1$.

То есть условие делимости сводится к:

3) Посчитаем порядок числа 10 по модулю 729

Заметим, что $729 = 3^6$, а $\gcd(10,729)=1$, значит можно пользоваться свойствами степеней по модулю.

Известно (и легко проверяется на малых степенях 3), что:

• $10 \equiv 1 \pmod{9}$,

• но по более высокой степени тройки это уже не так.

Посчитаем аккуратно ключевые степени:

Шаг 1: $10^3$ по модулю 27

Значит

Шаг 2: перейти к модулю 729
Рассмотрим $10^3 = 1 + 27k$, где $k=37$.
Тогда

Разложим по биному Ньютона по модулю 729. Нам важны только члены, которые могут не исчезнуть по модулю $729=27^2$.

• Первый добавочный член:

он точно кратен 729, значит исчезает по модулю 729.

• Любой член начиная со второго содержит $(27k)^2 = 729k^2$, то есть тоже кратен 729 и тоже исчезает.

Значит целиком:

То есть действительно:

4) Вывод

Получили, что $10^{81}-1$ делится на 729, а значит $\dfrac{10^{81}-1}{9}$ делится на 81.

Следовательно, число $111\ldots111$ (81 единица) делится на 81.