Suppose that $n = p_1p_2 \cdots p_k$, where $p_1, p_2, .\ldots, p_k$ are distinct odd primes. Show that $a^{φ(n)+1} ≡ a\pmod n$

Question

Question: Suppose that $n = p_1p_2 \cdots p_k$, where $p_1, p_2, \ldots , p_k$ are distinct odd primes. Show that $a^{φ(n)+1} ≡ a\pmod n$

So I assume since n contains a bunch of distinct odd primes, I'd say each value $pk$ is relatively coprime with one another.

So, $(p_i , p_j ) = 1 $

I have absolutely no clue where to go from here. Would I just use Fermat's Little Theorem from this point on? I'm only assuming FLT since $a^{φ(n)+1} ≡ a\pmod n$ seems to kind of be in the same form of $a^p ≡ a \pmod p$

Answer 1

This is Euler's theorem, an extension of lil' Fermat.

Hint: Use the Chinese remainder theorem: $$\mathbf Z/n\mathbf Z\simeq \mathbf Z/p_1\mathbf Z\times\mathbf Z/p_2\mathbf Z\times\dots\times\mathbf Z/p_k\mathbf Z.$$