Функция Эйлера и теорема Эйлера из ТЧ

Для начала заметим, что к числу с суммой цифр равной мы можем дописать сколько угодно нулей справа и при этом сумма цифр не изменится. Поэтому если , где НОД(, 10) = 1, то чтобы найти нужное число делящееся на , достаточно найти число делящееся на .

Вторая идея этого решения заключается в том, чтобы найти МНОГО чисел с суммой цифр 1 и остатком 1 по mod . Если мы найдем таких чисел и сложим их, то сумма цифр сложится (мы на это надеемся), и получившееся число будет сравнимо с по модулю , а .

В качестве одного из таких чисел можно взять (по теореме Эйлера (mod )) и тут время вспомнить о том, что сравнения можно возводить в степень, то есть (mod ), поэтому нам подойдет любое число вида . При сложении таких чисел в столбик из-за того, что единички у этих чисел будет в разных разрядах, получится число с суммой цифр и делящееся на . Осталось лишь дописать к этому число много (max(, )) нулей справа и получить число с суммой цифр и делящееся на .