Determine the number of integers for which the congruence is true

[lfdahl]

Determine the number of integers $n \geq 2$ for which the congruence $x^{25} \equiv x$ $(mod \;\; n)$ is true for all integers $x$.

 

[castor28]

Determine the number of integers $n \geq 2$ for which the congruence $x^{25} \equiv x$ $(mod \;\; n)$ is true for all integers $x$.

[sp]
Let us look first at a prime divisor $p$ of $n$. If $x\equiv0\pmod{p}$, the congruence is obviously satisfied. Otherwise, we may cancel $x$ and get $x^{24}\equiv1\pmod{p}$.

This congruence will be satisfied if $o(x)\mid24$, where $o(x)$ is the multiplicative order of $x$ modulo $p$. If we take $x$ as a primitive root modulo $p$, we have $o(x)=p-1$, by Fermat's theorem, and this shows that we must have $p-1\mid 24$. Since $o(x)\mid p-1$ for any $x\not\equiv0$, the condition is sufficient as well (if $n=p$).

The primes $p$ such that $p-1\mid 24$ are 2, 3, 5, 7, and 13.

By the Chinese Remainder Theorem, any product of distinct primes from this set will satisfy the congruence for all $x$.

Now, $n$ cannot be divisible by the square of a prime $p$, because the congruence would fail for $x=p$: $p^{25}\equiv0\not\equiv p\pmod{p^2}$.

To summarize, the only integers $n\ge2$ that satisfy the condition are the products of distinct integers from the set $\{2,3,5,7,13\}$; there are $2^5-1=31$ such integers.
[/sp]

 

[lfdahl]

[sp]
Let us look first at a prime divisor $p$ of $n$. If $x\equiv0\pmod{p}$, the congruence is obviously satisfied. Otherwise, we may cancel $x$ and get $x^{24}\equiv1\pmod{p}$.

This congruence will be satisfied if $o(x)\mid24$, where $o(x)$ is the multiplicative order of $x$ modulo $p$. If we take $x$ as a primitive root modulo $p$, we have $o(x)=p-1$, by Fermat's theorem, and this shows that we must have $p-1\mid 24$. Since $o(x)\mid p-1$ for any $x\not\equiv0$, the condition is sufficient as well (if $n=p$).

The primes $p$ such that $p-1\mid 24$ are 2, 3, 5, 7, and 13.

By the Chinese Remainder Theorem, any product of distinct primes from this set will satisfy the congruence for all $x$.

Now, $n$ cannot be divisible by the square of a prime $p$, because the congruence would fail for $x=p$: $p^{25}\equiv0\not\equiv p\pmod{p^2}$.

To summarize, the only integers $n\ge2$ that satisfy the condition are the products of distinct integers from the set $\{2,3,5,7,13\}$; there are $2^5-1=31$ such integers.
[/sp]

Amazing, castor28! Thankyou very much for your sharp-minded deduction! (Cool)