Произведение двух чисел без нулей

[Ktina]

Можно ли представить число $100^{2011}$ в виде произведения двух натуральных чисел, не содержащих нулей в десятичной записи?

(Румынская Математическая Олимпиада)

[Dave]

Нет, нельзя. Если бы было можно, т.е. $100^{2011}=2^{4022} \cdot 5^{4022}=ab$, то $2$ и $5$ не могли бы входить одновременно в разложение одного из чисел $a$ или $b$ на простые множители, иначе это число оканчивалось бы на $0$. Значит одно из этих чисел должно быть равно $2^{4022}$, а другое - $5^{4022}$.
Но не тут-то было! Ведь $2^{20}=1048576 \equiv 76 \pmod {100}$, а $2^{22}=4194304 \equiv 4 \pmod {100}$. Отсюда следует, что $2^{20+22} \equiv 76 \cdot 4 \equiv 4 \pmod {100}$, и вообще $2^{20n+22} \equiv 4 \pmod {100}$, если $n$ - натуральное (доказывается по индукции). В частности $2^{4022} \equiv 4 \pmod {100}$, т.е. предпоследняя цифра этого числа есть $0$.