Малая теорема Ферма

[RIP]

Несложная, но симпатичная задачка:
Найти все натуральные числа $n$ такие, что для всех целых $a$ выполняется

$$a^{n+1}\equiv a\pmod n.$$

[maxal]

Нетрудно, видеть, что $n>1$ обязано быть четно, а $\frac{n}{2}$ - нечетно.
Кроме того, если нечетное простое $p$ делит $n,$ то $p-1$ также делит $n.$ Эти условия необходимы и достаточны.

[RIP]

maxal писал(а):

Нетрудно, видеть, что $n>1$ обязано быть четно, а $\frac{n}{2}$ - нечетно.
Кроме того, если нечетное простое $p$ делит $n,$ то $p-1$ также делит $n.$ Эти условия необходимы и достаточны.

Эти условия не являются достаточными.

[Руст]

1. rad(n)=n. Если n делится на вторую степень простого числа p, взяв a=p получаем противоречие.
2. $\phi(n)|n$ это очевидно.
3. Если p максимальный простой делитель, то $\phi(\frac np )|\phi(n)|\frac{n}{p}$, т.е. n/p так же решение.
4. Нечётных простых делителей не больше одного, иначе $4|\phi(n)\not |n$, так как n не делится на 4.
Одно решение n=1. Допустим, что n>1. Взяв минимальный простой делитель n получаем, что он равен 2. это дает второе решение n=2. Соответственно получаем третье решение n=2*3. В соответствии с доказанным других решений нет.

[RIP]

Руст писал(а):

2. $\phi(n)|n$ это очевидно.

Возможно. Но это неверно.

[maxal]

Да, еще нужна свободность от квадратов. А дальше как здесь.

Получается конечное число решений: 1, 2, 6, 42, 1806

[Руст]

RIP писал(а):

Руст писал(а):

2. $\phi(n)|n$ это очевидно.

Возможно. Но это неверно.

Да. Надо было писать $n=p_1p_2...p_k, gcd(p_1-1,p_2-1,...,p_k-1)|n$. Ошибки обычно делаем там, где очевидною
Соответственно, все простые имеют вид 4к+3. Получаем четвёртое решение 42 и пятое решение 42*43.