MHB Determine the number of integers for which the congruence is true

  • Thread starter Thread starter lfdahl
  • Start date Start date
  • Tags Tags
    Integers
Click For Summary
The congruence \( x^{25} \equiv x \pmod{n} \) holds for all integers \( x \) if \( n \) is a product of distinct primes \( p \) such that \( p-1 \) divides 24. The relevant primes are 2, 3, 5, 7, and 13. Additionally, \( n \) cannot include the square of any prime, as this would violate the congruence for \( x = p \). By the Chinese Remainder Theorem, any combination of these primes will satisfy the condition, resulting in 31 valid integers \( n \geq 2 \). The analysis concludes that the integers satisfying the congruence are precisely those products of the specified primes.
lfdahl
Gold Member
MHB
Messages
747
Reaction score
0
Determine the number of integers $n \geq 2$ for which the congruence $x^{25} \equiv x$ $(mod \;\; n)$ is true for all integers $x$.
 
Mathematics news on Phys.org
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$.
[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]
 
Last edited:
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]

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

Similar threads

  • · Replies 17 ·
Replies
17
Views
2K
Replies
9
Views
2K
Replies
1
Views
1K
  • · Replies 2 ·
Replies
2
Views
1K
Replies
4
Views
2K
Replies
1
Views
2K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 15 ·
Replies
15
Views
2K