尤拉函式（φ函式）計算器

輸入整數 N（1〜1,000,000），立即計算1到N之間與N互質的整數個數（尤拉函式 φ(N)），並顯示質因數分解與計算公式。附帶1〜100的φ(n)速查表。

1〜100 的φ(n)速查表

彙總了1到100的每個整數的質因數分解與尤拉函式值的一覽表。

N 質因數分解 φ(n)
1 1 1
2 2 1
3 3 2
4 2² 2
5 5 4
6 2 × 3 2
7 7 6
8 2³ 4
9 3² 6
10 2 × 5 4
11 11 10
12 2² × 3 4
13 13 12
14 2 × 7 6
15 3 × 5 8
16 2⁴ 8
17 17 16
18 2 × 3² 6
19 19 18
20 2² × 5 8
21 3 × 7 12
22 2 × 11 10
23 23 22
24 2³ × 3 8
25 5² 20
26 2 × 13 12
27 3³ 18
28 2² × 7 12
29 29 28
30 2 × 3 × 5 8
31 31 30
32 2⁵ 16
33 3 × 11 20
34 2 × 17 16
35 5 × 7 24
36 2² × 3² 12
37 37 36
38 2 × 19 18
39 3 × 13 24
40 2³ × 5 16
41 41 40
42 2 × 3 × 7 12
43 43 42
44 2² × 11 20
45 3² × 5 24
46 2 × 23 22
47 47 46
48 2⁴ × 3 16
49 7² 42
50 2 × 5² 20
51 3 × 17 32
52 2² × 13 24
53 53 52
54 2 × 3³ 18
55 5 × 11 40
56 2³ × 7 24
57 3 × 19 36
58 2 × 29 28
59 59 58
60 2² × 3 × 5 16
61 61 60
62 2 × 31 30
63 3² × 7 36
64 2⁶ 32
65 5 × 13 48
66 2 × 3 × 11 20
67 67 66
68 2² × 17 32
69 3 × 23 44
70 2 × 5 × 7 24
71 71 70
72 2³ × 3² 24
73 73 72
74 2 × 37 36
75 3 × 5² 40
76 2² × 19 36
77 7 × 11 60
78 2 × 3 × 13 24
79 79 78
80 2⁴ × 5 32
81 3⁴ 54
82 2 × 41 40
83 83 82
84 2² × 3 × 7 24
85 5 × 17 64
86 2 × 43 42
87 3 × 29 56
88 2³ × 11 40
89 89 88
90 2 × 3² × 5 24
91 7 × 13 72
92 2² × 23 44
93 3 × 31 60
94 2 × 47 46
95 5 × 19 72
96 2⁵ × 3 32
97 97 96
98 2 × 7² 42
99 3² × 11 60
100 2² × 5² 40

Tips

  • 尤拉函式 φ(n)表示1到n之間與n互質的整數個數。例如 φ(9) = 6（1, 2, 4, 5, 7, 8 這6個數與9互質）。
  • 當n是質數p時，φ(p) = p − 1，因為除p自身外，1到p之間的所有數都與質數互質。
  • 當n是兩個不同質數p、q的乘積時，φ(pq) = (p−1)(q−1)，這一性質直接用於RSA加密的金鑰生成。
  • 公式 φ(n) = n × Π(1 − 1/p) 是對n的所有不同質因數p的連乘積，質因數的指數不影響結果。
  • 本工具支援1〜1,000,000的範圍，使用試除法進行質因數分解，可即時求出φ(n)。

常見問題

除了作為數論的基礎理論外，它在密碼學中也扮演核心角色，尤其是RSA加密的金鑰生成。RSA加密計算私鑰時會用到 φ(n) = (p−1)(q−1) 的值。

按照慣例，規定 φ(1) = 1。雖然「與1互質且不超過1的整數」只有1本身，但為了保持函式作為「乘法函式」的一致性，數學上標準做法是定義φ(1) = 1。

是的。質數p除了1和p自身外沒有其他約數，因此1到p之間除p以外的所有數都與p互質，即 φ(p) = p − 1。

RSA加密將兩個大質數p、q的乘積 n = pq 作為公鑰的一部分。計算私鑰需要 φ(n) = (p−1)(q−1) 的值，但若不能對n進行質因數分解就無法求出φ(n)，大數分解的困難性正是RSA加密安全性的基礎。
ツールくん

閒話 ― 18世紀尤拉發現的「互質計數」函式

尤拉函式（φ函式）據稱是18世紀瑞士數學家萊昂哈德·尤拉在1763年前後提出的，最初是在將費馬小定理推廣到合數的過程中被研究的。如今通用的符號φ（phi）是後來的數學家整理記號體系後才固定下來的。

「統計互質數」看似樸素，但φ(n)有許多優美的性質。例如，將n的所有約數d的φ(d)相加，結果必然等於n本身（Σφ(d) = n），這是初等數論中的一個基本恆等式。

如今，φ(n)在RSA加密中扮演著不可或缺的角色。RSA加密使用兩個大質數p、q的乘積 n = pq 作為公鑰的一部分，而計算私鑰則需要 φ(n) = (p−1)(q−1) 的值。只要無法對n進行質因數分解就無法求出φ(n)（至少目前已知的演算法如此），這正是RSA加密安全性的基礎之一。

閱讀相關趣味知識

檢視全部趣味知識

檢視此工具的人也看了

質數判斷器（免費）- 支援1000位、含質因數分解

輸入最多 1000 位的數字即可立即判斷是否為質數。同時顯示質因數分解、前後相鄰的質數、試除法步驟，以及本次結論由哪種判定法得出。免費、無需註冊。

埃拉托斯特尼篩法生成器（免費）- 質數一覽・第N個質數查詢

只需輸入上限N，即可使用埃拉托斯特尼篩法逐步視覺化生成質數一覽。除1至100早見表外，還支援最大100萬範圍及第100萬個質數等大序數的反向查詢，免費、無需註冊、瀏覽器內直接計算。

質因數分解計算器（免費線上工具，2至1,000,000）

免費線上工具，立即將任意整數 N（2〜1,000,000）分解為質因數。顯示逐步除法過程、因數列表、因數個數及因數和。附1〜100質因數分解速查表。

最大公約數・最小公倍數計算器

輸入兩個正整數後，用輾轉相除法（歐幾里得演算法）求出最大公約數（GCD），並逐步顯示計算過程。同時計算出最小公倍數（LCM）。

模運算計算器（Mod 計算器）

支援4種模式的模運算計算器：基本mod、模加減乘運算、模冪運算（快速冪/平方求冪法）、模逆元（擴充套件歐幾里得演算法）。使用 BigInt 精確處理負數取模和超大指數運算。

中國剩餘定理（CRT）計算器 — 求解一次同餘方程組

使用中國剩餘定理求解形如 x ≡ a₁ (mod n₁)、x ≡ a₂ (mod n₂)… 的同餘方程組。自動驗證各模數是否兩兩互素，並給出最小非負整數解與通解。