Carmichael函数是这样一个定义的函数 phi(n)=所有小于n且和n互质的数的数量，举个糖炒栗子： phi(6)=2 因为只有1,5 <6且和6互质。明眼人就可以看出来了，如果phi(p) p是个质数，那么显然phi(p)=p-1，因为肯定是从1数到p-1都是和p互质的。

好了，那么现在一个关键的问题，phi(pq) ，在 p，q都是质数是怎么样的形式？

肯定也是要数出所有和pq互质的数，那么怎么数？

我们假设 x是一个和pq互质的，那么显然 gcd(x,pq)=1, 因为p，q都是质数，那么显然根据中国剩余定理在循环群Z/q 和Z/p上可以形成群积同构，并且同构于循环群Z/pq。 则显然，根据中国剩余定理，必然存在一个且仅有一个l=x mod p,和仅有一个m =x mod q, 而l, m则显然是属于在phi(p) phi (q)里被数过的数字，这个是根据中国剩余定理的1-1对应可以确定。那么显然，所有像 x这样的数字的数量，必然会是phi(p)的倍数，也会是phi(q)的倍数，且是最小倍数值（否则越界到 1=mod p ,1=mod q里去了）

则显然 phi(pq)=lcm (phi(p),phi (q)) 又因为p, q都是质数，则显然

phi(pq)=lcm (p-1,q-1)

上面这个结论必须牢记，因为下一步的密钥生成就是要根据上面的这个结论来做的。