1. ## Euler's Theorem

I am trying to prove a little modification on Euler's theorem

$\displaystyle 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.

$\displaystyle a^{\phi(n)} \equiv 1 (mod n)$
$\displaystyle a * a^{\phi(n)} \equiv a (mod n)$
$\displaystyle 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!

2. You can work with Euler's Theorem, yes.

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

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

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

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

Then $\displaystyle 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 $\displaystyle a^{\phi(n)+1}\equiv{p^{s\cdot{(\phi(n)+1)}}\cdot{k }}(\bmod.n)$

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

And this is true since $\displaystyle p^{s\cdot{\phi(n)}}-1\equiv{0}(\bmod.q)$ by Euler's Theorem ( remember that $\displaystyle \phi(n)=\phi(p)\cdot{\phi(q)}$ )

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

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

Remember the rule that two congruences which are congruent to the same number are congruent to eachother, and so, $\displaystyle a^{\phi(n)+1} \equiv a(\bmod n)$.

5. Ahh, perfect I got it now! Thanks!