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

• MHB
• lfdahl
In summary, there are 31 integers $n \geq 2$ that satisfy the congruence $x^{25} \equiv x$ $(mod \;\; n)$ for all integers $x$. These integers are products of distinct primes from the set $\{2,3,5,7,13\}$. This is determined by looking at prime divisors of $n$ and using the Chinese Remainder Theorem.
lfdahl
Gold Member
MHB
Determine the number of integers $n \geq 2$ for which the congruence $x^{25} \equiv x$ $(mod \;\; n)$ is true for all integers $x$.

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)

## 1. How do you determine the number of integers for which the congruence is true?

The number of integers for which the congruence is true can be determined by using the Chinese Remainder Theorem or by finding the least common multiple of the given moduli.

## 2. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that provides a method for solving a system of congruences with pairwise relatively prime moduli.

## 3. Can the number of integers for which the congruence is true be infinite?

Yes, the number of integers for which the congruence is true can be infinite. This is usually the case when the moduli are not relatively prime, and the congruence has a periodic pattern.

## 4. What is the least common multiple of moduli in a congruence?

The least common multiple of moduli is the smallest positive integer that is divisible by all the given moduli. It is used to determine the number of integers for which the congruence is true.

## 5. Are there any other methods for finding the number of integers for which the congruence is true?

Yes, there are other methods such as using modular arithmetic and the Euler's totient function. These methods are useful when the moduli are not relatively prime.

• General Math
Replies
17
Views
1K
• General Math
Replies
4
Views
697
• General Math
Replies
15
Views
2K
• General Math
Replies
1
Views
1K
• General Math
Replies
5
Views
2K
• General Math
Replies
1
Views
970
• General Math
Replies
1
Views
794
• General Math
Replies
2
Views
1K
• General Math
Replies
2
Views
1K
• General Math
Replies
13
Views
1K