Олимпиадная задача по теории чисел: шестизначное число без шести одинаковых последних цифр
Задача
Существует ли такое шестизначное число A, что среди чисел A, 2A, ..., 500000A нет ни одного числа, оканчивающегося шестью одинаковыми цифрами?
Решение
Решение 1: Пусть A взаимно просто с 10. Тогда числа A, 2A, ..., 106A дают при делении на 106 все возможные остатки по одному разу (см. зад. 160733). Поэтому достаточно найти такое число A, что остатки 111111, 222222, ..., 999999 появятся на девяти последних местах, то есть у чисел от (106 – 9)A до (106 – 1)A.
Возьмём A = 888889 ≡ – 111111 (mod 106). Тогда (106 – m)A ≡ – mA ≡ 111111m (mod 106).
Решение 2: Возьмём A = 999997 = 106 – 3. Пусть kA оканчивается шестью одинаковыми цифрами, то есть имеет вид 106m + 111111n (n = 0, 1, ..., 9). Тогда
(106 – 3)k = 106m + 3·37037n или 106(k – m) = 3·(k + 37037n). Поэтому k + 37037n делится на 106. Следовательно, k + 37037n ≥ 106, откуда
k ≥ 106 – 37037·9 > 500000.
Ответ
Существует.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь