Suppose n is a product of distinct odd primes. Show $a^{\phi(n)+1}\equiv a $ (mod $n$).

Question

Suppose n is a product of distinct odd primes. Show $a^{\phi(n)+1}\equiv a $ (mod $n$). Let $\phi(n)$ be the Euler Totient function.

I let $n = p_1p_2\cdot\cdot\cdot p_k$ for $p_i > 2$ and each of the $p_i$ are distinct.

I let $a = q_1^{r_1}q_2^{r_2}\cdot\cdot\cdot q_m^{r_m}$ for primes $q_i$.

There are two cases: either gcd(a, n) = 1 or gcd(a, n) is a product of some of the primes.

I can easily figure Case 1 by using Euler's Theorem and the Chinese Remainder Theorem.

I'm having problems figuring out the second case. Any suggestions of where I might start?

Answer 1

For $p_i,$ using Fermat's Little Theorem, $$p_i|a(a^{p_i-1}-1)$$

If $(a,p_i)=1,$ as $(p_i-1)|\phi(n),p_i|(a^{\phi(n)}-1)$

Else $p_i|a\implies p_i|a(a^{\phi(n)}-1)$

$\implies p_i|a(a^{\phi(n)}-1)$ for all integer $a$

This holds true for $1\le i\le k$

$\implies a(a^{\phi(n)}-1)$ will be divisible by lcm$(p_i;1\le i\le k)$