The Chinese Remainder when the residues are 1

elementary-number-theorymodular arithmeticnumber theory

$\newcommand{\mod}{\operatorname{mod}}$I'm trying to understand how the Euler Theorem is generalized to any number.
So we have $n$ as a multiplication of powers of prime number.
I can prove that an m is multiple of all the Euler phi-functions of the powers of the prime numbers $p_i^{s_i}$, so I have $a^m \equiv 1\, (\mod p_i^{s_i})$ for any prime number power composing n.

I just can not understand how can I prove $a^m \equiv 1\, (\mod n)$. How can I make the passage?

Everyone just writes: by using the Chinese Remainder Theorem. I have read the theorem and the proof so many times and I just don't see how to explain the logic of the passage.

Best Answer

The Chinese remainder theorem tells you that given a system of linear congruence of the form $$x\equiv a_k\pmod{m_k}\ k=1,2,\dots,N$$ where the moduli $m_1,m_2,\dots,m_N$ are pairwise relatively prime, the system has exactly one solution modulo $m_1m_2\cdot\dots\cdot m_N$. You have such a system, and you can see that the proposed solution satisfies each of the congruences, so it is the only solution modulo the product of the moduli, which is $n$ in your case.

Related Question