歐拉函數

設想從 1 到 n 這些數，問其中有多少個與 n 互不相干 — 即與 n 沒有公因數。歐拉函數所度量的正是這個計數：它統計該範圍內與 n 互質的整數個數。

記作 φ(n)（希臘字母 phi），它是滿足 1 ≤ k ≤ n 且 gcd(k, n) = 1 的整數 k 的個數。對質數 p，每個比它小的正數都與它互質，所以 φ(p) = p − 1。該函數對互質的自變量是積性的 — 當 gcd(m, n) = 1 時 φ(m n) = φ(m) φ(n) — 而對質數冪，φ(p^k) = p^k − p^(k−1)。把這些結合起來，便得到由質因數分解給出的公式：φ(n) = n 乘以所有整除 n 的質數 p 的 (1 − 1/p) 之積。

歐拉函數是歐拉定理 a^(φ(n)) ≡ 1 (mod n)（a 與 n 互質）的支柱，而後者又是 RSA 密碼體制的基礎。一個常見的絆腳石：當兩個自變量有公因數時 φ 並非積性 — φ(2 乘以 2) = φ(4) = 2，而不是 φ(2) 乘以 φ(2) = 1 — 所以積性這一性質嚴格要求自變量互質。