CRT as a ring isomorphism and the multiplicativity of $\varphi$
Statement
When , the map is a ring isomorphism , and restricting to invertible elements proves .
Why is it true?
This is the structural meaning of CRT: arithmetic modulo literally is two independent copies of modular arithmetic (one mod , one mod ) running side by side. That is both why Euler's totient 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, is well-defined: if then , so both and divide , meaning and .
Second, respects addition and multiplication in each coordinate because reduction modulo does (proved in the first topic on congruences), so is a ring homomorphism.
Third, Theorem 1 above says precisely that for every pair there is an mapped to it (so is surjective) and that is unique modulo (so is injective). Hence is a bijection and therefore a ring isomorphism.
Finally, in a product ring , an element has a multiplicative inverse iff in and in — that is, iff both coordinates are invertible. Since a ring isomorphism preserves invertibility, the invertible elements of (of which there are ) correspond bijectively to pairs of invertible elements in (of which there are ). Counting both sides gives . Combined with for a prime power (where the non-coprime numbers are just the multiples of ), this immediately yields the general product formula for used in the previous topic.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Jean-Jacques Quisquater, Christophe Couvreur (1982). Fast decipherment algorithm for RSA public-key cryptosystem · DOI:10.1049/el:19820617
- David Harvey, Joris van der Hoeven (2021). Integer multiplication in time O(n log n) · DOI:10.4007/annals.2021.193.2.4