MathLabs
TheoremProved

CRT as a ring isomorphism and the multiplicativity of $\varphi$

Statement

When gcd⁡(m1,m2)=1\gcd(m_1,m_2)=1, the map ψ(x mod m1m2)=(x mod m1, x mod m2)\psi(x \bmod m_1 m_2) = (x\bmod m_1,\ x\bmod m_2) is a ring isomorphism Z/(m1m2)Z≅(Z/m1Z)×(Z/m2Z)\mathbb{Z}/(m_1 m_2)\mathbb{Z} \cong (\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z}), and restricting ψ\psi to invertible elements proves φ(m1m2)=φ(m1) φ(m2)\varphi(m_1 m_2) = \varphi(m_1)\,\varphi(m_2).

Why is it true?

This is the structural meaning of CRT: arithmetic modulo m1m2m_1 m_2 literally is two independent copies of modular arithmetic (one mod m1m_1, one mod m2m_2) running side by side. That is both why Euler's totient φ\varphi factors cleanly across coprime numbers, and why computers can speed up big-integer and cryptographic calculations by doing them in each small component separately.

Proof sketch

First, ψ\psi is well-defined: if x≡x′(modm1m2)x\equiv x'\pmod{m_1 m_2} then m1m2∣(x−x′)m_1 m_2\mid(x-x'), so both m1m_1 and m2m_2 divide x−x′x-x', meaning x≡x′(modm1)x\equiv x'\pmod{m_1} and x≡x′(modm2)x\equiv x'\pmod{m_2}.

Second, ψ\psi respects addition and multiplication in each coordinate because reduction modulo mim_i does (proved in the first topic on congruences), so ψ\psi is a ring homomorphism.

Third, Theorem 1 above says precisely that for every pair (a1,a2)(a_1,a_2) there is an xx mapped to it (so ψ\psi is surjective) and that xx is unique modulo m1m2m_1 m_2 (so ψ\psi is injective). Hence ψ\psi is a bijection and therefore a ring isomorphism.

Finally, in a product ring R1×R2R_1\times R_2, an element (u1,u2)(u_1,u_2) has a multiplicative inverse (v1,v2)(v_1,v_2) iff u1v1=1u_1 v_1=1 in R1R_1 and u2v2=1u_2 v_2=1 in R2R_2 — that is, iff both coordinates are invertible. Since a ring isomorphism preserves invertibility, the invertible elements of Z/(m1m2)Z\mathbb{Z}/(m_1 m_2)\mathbb{Z} (of which there are φ(m1m2)\varphi(m_1 m_2)) correspond bijectively to pairs of invertible elements in (Z/m1Z)×(Z/m2Z)(\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z}) (of which there are φ(m1) φ(m2)\varphi(m_1)\,\varphi(m_2)). Counting both sides gives φ(m1m2)=φ(m1) φ(m2)\varphi(m_1 m_2)=\varphi(m_1)\,\varphi(m_2). Combined with φ(pr)=pr−pr−1\varphi(p^r)=p^r-p^{r-1} for a prime power (where the non-coprime numbers are just the pr−1p^{r-1} multiples of pp), this immediately yields the general product formula for φ(n)\varphi(n) used in the previous topic. ■\blacksquare

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Jean-Jacques Quisquater, Christophe Couvreur (1982). Fast decipherment algorithm for RSA public-key cryptosystem · DOI:10.1049/el:19820617
  2. David Harvey, Joris van der Hoeven (2021). Integer multiplication in time O(n log n) · DOI:10.4007/annals.2021.193.2.4