最大公因數: gcd(a, b)，可以利用gcd判斷兩個整數是不是互質: a \perp b: gcd(a, b) = 1，若兩數互質代表兩數的最大公因數就是1。

一個合成數n可以拆成質數分解: n = p_{1}^{e_{1}-1}p_{}2^{e_{2}-1}\cdot\cdot\cdot p_{k}^{e_{k}}，每個p都只會出現一次。

有了前面幾種工具，就可以建構出尤拉函數:

\varphi(n) = \| \{x | x \perp n, 1 \leq x \leq n-1 \} \| = p_{1}^{e_{1}-1}p_{}2^{e_{2}-1}\cdot\cdot\cdot p_{k}^{e_{k}-1}(p_{1}-1)(p_{2}-1) \cdot\cdot\cdot (p_{k}-1)

尤拉函數能夠幫助我們快速找出在n之下所有與n互質的整數個數。