Question

Какое минимальное количество цифр может быть в числе 111...11, если известно что оно делится на 99?

Answer 1

Ответ:

18

Пошаговое объяснение:

Если число делится на 99, то оно делится на 11 и 9.  Если число делится на 9, то сумма его цифр делится на 9. Значит число 111...11 состоит из 9*N единиц. При этом, оно будет делится на 11  только, если количество единиц в числе четное. Значит в искомом числе 9*2=18 единиц.

Answer 2

Число, состоящее из одних единиц (например, 111...11), может быть представлено как $10^n - 1$, где $n$ - количество цифр единиц в числе. Если это число делится на 99, то оно также должно делиться на $9 \times 11$, так как 99 разлагается на простые множители $9$ и $11$.

Проверим условие деления на $9$: $10^n - 1 \equiv 1^n - 1 \equiv 0 \pmod{9}$ Это условие выполняется, когда $n$ делится на 9.

Проверим условие деления на $11$: $10^n - 1 = (10^9)^{\frac{n}{9}} - 1$ По малой теореме Ферма: $a^{p-1} \equiv 1 \pmod{p}$ для любого простого $p$, не делящего $a$. В данном случае $p = 11$ и $a = 10^9$. Таким образом: $(10^9)^{\frac{n}{9}} - 1 \equiv 1^{\frac{n}{9}} - 1 \equiv 0 \pmod{11}$

Итак, чтобы число состояло только из единиц и делилось и на 9, и на 11, необходимо, чтобы $n$ было кратно и 9, и 1 (то есть просто кратно 9). Таким образом, минимальное значение $n$ будет 9, и число будет иметь девять цифр единиц:

$111111111$