数论引理证明,欧拉函数求证下面引理：若n=n1×n2,且n1,n2互素,则φ（n）=φ(n1)×φ(n2)其中φ(m)=

套用结论的话,就是用中国剩余定理:
同余方程组x ≡ a (mod n1),x ≡ b (mod n2)在mod n意义下存在唯一解x ≡ c (mod n).
这样建立了{0,1,...,n1-1}×{0,1,...,n2-1} → {0,1,...,n-1}的单射,
比较元素个数可知这也是双射.
由c ≡ a (mod n1),c ≡ b (mod n2),n = n1·n2.
可验证(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
因此上述映射刚好给出A×B → C的双射.
用Bezout定理可以给出构造的细节.
由(n1,n2) = 1,存在整数u,v,满足n1·u+n2·v = 1.
可验证c = n1·ub+n2·va即满足c ≡ a (mod n1),c ≡ b (mod n2),
且c mod n的余数不依赖u,v的选取.
此外(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
构造映射将(a,b)映为c mod n的余数,可验证其为A×B → C的双射.