Euler gone wild!

Number Theory Level 3

$\large a^{11762}\equiv{a^2}\pmod{25725}$

Find the smallest positive integer $a$ such that the congruency above fails to hold.

The answer is 7.

4 solutions

Otto Bretscher
May 20, 2015

Let me try to summarize Gian's solution.

We have the prime factorization $n=25725=3(5^2)(7^3)=3\times{25}\times{343}$ . The given congruency holds modulo 25725 if (and only if) it holds modulo 3, 25, and 343.

Let's look at the congruency modulo 25 first. If 5 does not divide $a$ , then Euler's theorem gives $a^{\phi(25)}=a^{20}\equiv1 \pmod{25}$ so $a^{11760}=a^{20\times588}\equiv1$ and $a^{11762}\equiv{a^2}$ as claimed. If 5 does divide $a$ , then 25 divides $a^2$ , so that $a^{11762}\equiv{0}$ $\equiv{a^2}\pmod{25}.$

The examination of the congruency modulo 3 is analogous.

Thus far, we see that the congruency $a^{11762}\equiv{a^2}$ holds for all $a$ modulo 3 and modulo 25.

Let' s now look at the congruency modulo 343. If 7 does not divide $a$ , then Euler's theorem gives $a^{\phi(343)}=a^{294}\equiv1 \pmod{343}$ so $a^{11760}=a^{294\times40}\equiv1$ and $a^{11762}\equiv{a^2}$ as claimed. If 7 divides $a$ , with multiplicity 1, then $a^{11762}\equiv{0}$ $\not\equiv{a^2}\pmod{343}.$

Thus $a=7$ is the smallest positive integer where the congruency fails. More generally, it fails if and only if $a$ has the prime factor 7 with multiplicity 1 (meaning that $a$ fails to be divisible by 49).

It seems that my dumb approach would be more suitable here!

"Is it 1? No. Is it 2? No. Is it 3? No.... Is it 7? Yes."

Although one can easily rule out 2 and 4 to be solutions by Euler's totient function and the obvious number 1, thus reduces the cases to the mere $\{3,5,6,7\}$ .

Pi Han Goh - 6 years ago

Very true indeed. I was taking a more systematic (and tedious?) approach to find all the $a$ for which the congruency does and does not hold.

This Corollary to Euler's Theorem may also shed some light on the matter. It shows that the congruency holds modulo 3 and 25, so that we can focus on modulo $7^3$ right away.

"Not to change the subject": Are you going to write a solution to this one ? We don't have a solution yet, and you seem just the right person for the task... ;)

Otto Bretscher - 6 years ago

Nah, my original solution is too long winded, I can't think of a better shortcut, plus I'm pretty sure I did a few hand waving assumptions.

I doubt I'm posting it anytime soon unless I got some creative ways to attack it.

Pi Han Goh - 6 years ago

How do you came to know about this

Raj Sancheti - 5 years, 4 months ago

Gian Sanjaya
May 20, 2015

25725 = 3 * 5^2 * 7^3. It's obvious then that 7 fails because 7^11762 is congruent to a multiple of 7^3 mod 25725 while 7^2 is not. By Fermat's Theorem we can prove that for "a" not divisible by 7 or divisible by 49, the congruency holds.

Thanks! You have the right idea.. For the benefit of the other members, you should still explain why the congruency holds for $a=3,4,5,6$ . You cannot apply Fermat's (or Euler's) Theorem directly in these cases since $a$ and $n=25725$ fail to be coprime.

Otto Bretscher - 6 years ago

Oh thanks! Wait, how about a=2? Hmm... I will need to prove that a^20 = 1 (mod 25) for a relatively prime with n (I meant the equal sign by equivalent, I don't know how to type the equivalent sign. Prove: a^4 = 1 (mod 5) for a relatively prime with 5 (other members can try each a=1,2,3,4 because it's relatively small) and then assume a^4=5n+1. Then, a^20 = (5n+1)^5 (mod 5) = (C(5,4) 5 n+1) (mod 5) (the reason is that other term has 5^x where x is an integer at least 2 and C(5,n) is always an integer for n integer between 0 and 5, inclusive). Since C(5,4)=5, a^20 = 5 5 n+1 (mod 5) = 1 (mod 5). And, a^11760 = (a^20)^588 = 1 (mod 25) (obviously from the previous prove) for a relatively prime with a and hence a^11762 = a^2 (mod 25) by multiplying each sides by a^2. This also hold for a multiple of 5, so the congruency hold for all integer a. Next, a^3 = a (mod 3) for all integer a (also able to be easily tried). Then, a^5 = a^3 * a^2 = a (a^2) (mod 3) = a^3 (mod 3). By the same reasoning, a^11761=a (mod 3) and then a^11762 = a^2 (mod 3). Thus, because a^11762 = a^2 (mod 3) and a^11762 = a^2 (mod 25), if a^11762 is not congruent a^2 mod 25725, then a^11762 is not congruent a^2 mod 343 (343 = 7^3). Hence, to prove that 7 is the smallest integer a so that the questioned statement holds, we need to prove that a^11760 = 1 (mod 343) for a not divisible by 7 (awww very long, I can just say in general we need to prove that a^((p-1)*p^(n-1)) = 1 (mod p^n)...) I would guess I will always miss something because usually I don't write things completely..

Gian Sanjaya - 6 years ago

Carsten Meyer
May 12, 2020

Let $n=25725=3^1\cdot 5^2\cdot 7^3$ and calculate the totient $\phi(n)=n\cdot\frac{2}{3}\cdot\frac{4}{5}\cdot\frac{6}{7}=11760$ . Factor out $a^2$ and rewrite the congruence to $\begin{aligned} f(a)&:=a^2(a^{\phi(n)}-1)\equiv 0 \mod n \end{aligned}$ We notice that $a,\:n$ must not be coprime: If they are, the second factor will be zero modulo $n$ by Euler's Theorem and the congruence holds! Of the first few such natural numbers $a\in\{3;\:5;\:6;\:7\}$ , only " $f(7)\not\equiv 0\mod n$ ", so the answer is $\boxed{7}$

Cantdo Math
Apr 10, 2020

The problem is equivalent to $a^2(a^{11760}-1)=0 (\mod 7^3*5^2*3)$ .It can be seen that a=7 can't work.Again, for this to not work a can't be coprime with 25725.Hence,only numbers left to check are 3 and 5.That's easy to check.

Euler gone wild!

The answer is 7.

4 solutions

0 pending reports