Advanced Number Theory

If the moduli are pairwise coprime, a system $x\equiv a_i\pmod{m_i}$ has a unique solution modulo $\prod m_i$.

In plain terms. Several "remainder" conditions with no shared factors always combine into a single condition — one remainder mod the product.

Example. $x\equiv 2\pmod 3$ and $x\equiv 3\pmod 5$ give $x\equiv 8\pmod{15}$ (check: $8 = 2\cdot3+2$ and $8 = 5+3$).

If $\gcd(a,n)=1$, then $a^{\varphi(n)}\equiv 1\pmod n$, where $\varphi(n) = n\prod_{p\mid n}(1-\tfrac1p)$.

In plain terms. Like Fermat but for any modulus: raising to the "totient power" resets to $1$. The totient counts how many numbers below $n$ share no factor with it.

Example. $\varphi(10) = 10(1-\tfrac12)(1-\tfrac15) = 4$, so $3^4 = 81\equiv 1\pmod{10}$.