Euler's totient function

https://en.wikipedia.org/wiki/Euler‘s_totient_function

 counts the positive integers up to a given integer n that are relatively prime to n. 

 if two numbers m and n are relatively prime, then φ(mn) = φ(m) φ(n);

https://zh.wikipedia.org/wiki/同餘

数学上，同余（英语：congruence modulo^[1]，符號：≡）是數論中的一種等價關係^[2]。當两个整数除以同一个正整数，若得相同余数，则二整数同余。同餘是抽象代數中的同餘關係的原型^[3]。最先引用同余的概念与「≡」符号者为德國数学家高斯。

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

In modular arithmetic, the modular multiplicative inverse of an integer a modulo m is

an integer x such that  a x ≡ 1 ( mod m ) .

Euler's totient function

原文：http://www.cnblogs.com/yuanjiangw/p/6115955.html