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

Очевидно, что для четных число точно не делится на . Поэтому число точно нечетное, НОД(, 2) = 1, а значит можно применить теорему Эйлера.

(mod ), значит если , то тогда нам подходит.

Понятно, что всегда хотя бы 1, так как для любого числа есть 1, которая не превосходит и взаимно проста с и всегда не больше , так как по определению равно количеству натуральных чисел от 1 до и взаимно простых с . Поэтому для всех нечетных существует требуемое в задаче