尤拉函數

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

一個合成數$n$可以拆成質數分解: $n = p_{1}^{e_{1}-1}p_{}2^{e_{2}-1}\cdots 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}\cdots p_{k}^{e_{k}-1}(p_{1}-1)(p_{2}-1) \cdots (p_{k}-1)$

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