Палиндром, кратный степени шестёрки

[Ktina]

Доказать, что любую степень шестёрки (с натуральным показателем) можно умножить на некоторое натуральное число так, что получится палиндром (в десятичной записи).

[Руст]

Это верно для всех чисел, не делящихся на 10. Впрочем последние так же удовлетворяют этому свойству, если спереди числа разрешить ставить необходимое количество нулей.

[Ktina]

Шесть лет прошло, а до доказательства мне так и не удалось додуматься.
Руст, может, хотя бы намекнёте, в чём там соль?

[Null]

Пусть $inv(A)$ - переворачивает число. Возьмем $inv(2^k)\cdot 10^k+2^k$. Повторяя его можно добиться деления на любое взаимно простое с 10

[Ktina]

Null
Большое спасибо!

[waxtep]

Null, Ktina, а почему это так ясно, что-то я туплю?

[Ktina]

waxtep
Мне пока неясно, я пытаюсь вникнуть.

[kotenok gav]

И я.

[Null]

Пусть $A$- многозначное число, рассмотрите остатки $A,AA,AAA\dots$ по модулю $m$ взаимно простому с 10 и используйте принцип Дирихле.

[DeBill]

Null в сообщении #1361409 писал(а):

Повторяя его можно добиться деления на любое взаимно простое с 10

Однако, это еще не решает задачу ("для любого, не кратного 10"): надо еще тот же фокус повторить с числами вида $5^k\cdot q $, где $q$ взаимно просто с 10....

[waxtep]

я, кажется, понял смысл конструкции:
1. Пусть дано $m=2^k\cdot p,5\not{\mid} p$ (двойку и пятерку здесь и далее можно поменять местами); мы ищем палиндром, который бы делился на $m$
2. Возьмем $A=\operatorname{inv}(2^k)\cdot10^k+2^k$ и последовательность палиндромов $A,AA,AA\,A,\ldots$; какие-то из них будут делиться на $m$, потому что там вылезет полная система остатков по модулю $p$

[DeBill]

waxtep в сообщении #1361704 писал(а):

какие-то из них будут делиться на $m$, потому что там вылезет полная система остатков по модулю $p$

Не, не вылезет, вааще говоря. Надо так: в этом списке есть числа с одинаковым остатком при делении на $p$. Тогда их разность делится на $p$. Но $p$ взаимно просто с 10 - значит, отбросив у разности нули, также получим число того же вида, делящееся на $p$. Но тогда это число делится и на $m$

[waxtep]

DeBill в сообщении #1361721 писал(а):

в этом списке есть числа с одинаковым остатком при делении на $p$. Тогда их разность делится на $p$.

ой, точно, спасибо!