10 различных цифр в числе, задача 739 из "Putnam and beyond"

[Xenia1996]

Для каждого простого числа $p$ существует бесконечно много натуральных чисел, кратных $p$, у каждого из которых все последние 10 цифр (в десятичной записи) являются попарно различными. Доказать.

Я предлагаю следующее решение:

(Оффтоп)

Рассмотрим бесконечную (в одну сторону) арифметическую прогрессию, состоящую из всех натуральных чисел вида $k\cdot10^{10}[phone]$, где $k$ - ЦНЧ (целое неотрицательное число).

Все члены элементы этой прогрессии кратны двум и пяти, так что для $p=2$ и для $p=5$ задача уже решена.

Если $p$ отличается от 2 и 5, то разность прогрессии взаимно проста с $p$, следовательно в прогрессии встретятся все возможные остатки при делении на $p$ (это надо здесь доказывать? а на олимпиаде?), причём каждый из них - бесконечно много раз.

Вроде, всё?

В книге "Putnam and beyond" предлагаются два иных решения, одно из которых опирается на МТФ.

[Sonic86]

Xenia1996 писал(а):

Если $p$ отличается от 2 и 5, то разность прогрессии взаимно проста с $p$, следовательно в прогрессии встретятся все возможные остатки при делении на $p$ (это надо здесь доказывать? а на олимпиаде?), причём каждый из них - бесконечно много раз.

Ну можно доказать, но это факт простой. На олимпиаде - желательно, жюри докопается.

-- Ср мар 02, 2011 11:47:48 --

По-моему, у Вас достаточно простое решение, вряд ли стоит выдумывать более сложное

[Sonic86]

МТФ наверное как раз используется для доказательства этого факта. Попробуйте его явно доказать - Вам полезно будет