The congruence \(x^{25} \equiv x \mod n\) holds for integers \(n \geq 2\) if and only if \(n\) is a product of distinct primes from the set \(\{2, 3, 5, 7, 13\}\). The necessary condition is derived from the requirement that \(p-1\) divides 24 for each prime divisor \(p\) of \(n\). The total number of such integers \(n\) is \(31\), calculated as \(2^5 - 1\), which accounts for all non-empty subsets of the prime set.
PREREQUISITESMathematicians, number theorists, and students studying modular arithmetic and prime factorization will benefit from this discussion.
[sp]lfdahl said: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 said:[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]