# Euler's Theorem

• November 18th 2008, 08:14 PM
apsis
Euler's Theorem
I am trying to prove a little modification on Euler's theorem

$a^{\phi(n)+1}\equiv a (mod n)$, for all a, and where n is the product of two distinct primes say p and q.

I am having problems with the for all a part as the above is easy to show.

$a^{\phi(n)} \equiv 1 (mod n)$
$a * a^{\phi(n)} \equiv a (mod n)$
$a^{\phi(n) + 1} \equiv a (mod n)$

I need to show that if q or p is a factor of a, then it still yields the same result, as Euler's theorem says that the gcd(a, n) must be 1. But I am not sure how to show that in the modification it doesn't matter. Any ideas?

Thanks!
• November 19th 2008, 12:39 AM
PaulRS
You can work with Euler's Theorem, yes.

Well, we have that if $(a,n)=1$ then $a^{\phi(n)}\equiv{1}(\bmod.n)$ and from there $a^{\phi(n)+1}\equiv{a}(\bmod.n)$ when $(a,n)=1$

Now if $(a,n)>1$ then $p|a$ and/or $q|a$. If both divide $a$ at the same time then $n|a$ and the assertion is obvious since $a\equiv{0}(\bmod.n)$ and so $a^{\phi(n)+1}\equiv{0}(\bmod.n)$

So assume that only one of the prime divides $a$, WLOG, becuase of the symmetry consider $p|a$

That is: $a=p^s\cdot{k}$ where $(k,n)=1$

Then $a^{\phi(n)}=p^{s\cdot{\phi(n)}}\cdot{k^{\phi(n)}}\ equiv{p^{s\cdot{\phi(n)}}}(\bmod.n)$ by Euler's Theorem. That is $a^{\phi(n)+1}\equiv{p^{s\cdot{(\phi(n)+1)}}\cdot{k }}(\bmod.n)$

So it all comes down to showing that $p^{s\cdot{(\phi(n)+1)}}\equiv{p^s}(\bmod.n)$ iff $p^s\cdot{(p^{s\cdot{\phi(n)}}-1)}\equiv{0}(\bmod.n)$

And this is true since $p^{s\cdot{\phi(n)}}-1\equiv{0}(\bmod.q)$ by Euler's Theorem ( remember that $\phi(n)=\phi(p)\cdot{\phi(q)}$ )
• November 19th 2008, 05:25 AM
apsis
Just to check we can say that $a^{\phi(n)+1} \equiv 0(mod \dot n)$ when n|a is the same as $a^{\phi(n)+1} \equiv a(mod \dot n)$ because $a \equiv a(mod \dot n)$ for all a right?
• November 19th 2008, 05:43 AM
ThePerfectHacker
Quote:

Originally Posted by apsis
Just to check we can say that $a^{\phi(n)+1} \equiv 0(mod \dot n)$ when n|a is the same as $a^{\phi(n)+1} \equiv a(mod \dot n)$ because $a \equiv a(mod \dot n)$ for all a right?

If $n|a$ then $a^{\phi(n)+1} \equiv 0(\bmod n)$ (because $n$ divides $a$).
And also $a\equiv 0(\bmod n)$.

Remember the rule that two congruences which are congruent to the same number are congruent to eachother, and so, $a^{\phi(n)+1} \equiv a(\bmod n)$.
• November 19th 2008, 05:47 AM
apsis
Ahh, perfect I got it now! Thanks!