尤拉函式（φ函式・互質數個數）計算器

輸入整數 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

什麼是歐拉函數

歐拉函數（totient 函數）φ(n) 表示1到 n 的整數中與 n 互質者共有多少個。互質是指最大公因數為1，也就是不含共同的質因數。例如 φ(9)，即數出與9沒有共同質因數的 1、2、4、5、7、8 這六個，故為6。

本工具只需填入整數 N 即可求出 φ(N)，並且不僅給出答案，還會一併列出 **N 的質因數分解，以及由此導出 φ(N) 的計算式**。計算式為 φ(n) = n × Π(1 − 1/p)，其中 p 為 n 的相異質因數。同一質因數無論作幾次方，在乘積中只出現一次，指數不影響結果。適用範圍為1至1,000,000，並附有1至100的 φ(n) 速查表。

歐拉函數計算器的使用方式

輸入整數 N 填入1以上1,000,000以下的整數。超出範圍或非整數的值會給出錯誤提示。
讀取 φ(N) 的值輸入的同時即顯示1〜N 中與 N 互質的整數個數。
確認質因數分解會顯示 N 分解為哪些質數之積，可作為追溯 φ(N) 之值由來的線索。
循計算式追蹤推導會顯示把實際質因數代入 φ(n) = n × Π(1 − 1/p) 後的算式，可直接用於手算的驗算。
用速查表與其他值比對下方列有1至100的 φ(n) 一覽。諸如「為質數時等於 n − 1」這類規律，皆可用肉眼確認。

用好本工具的小技巧

尤拉函式 φ(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)。

歐拉函數派上用場的情境

數論的學習與作業驗算

可確認手算所得的 φ(n) 是否正確。因並列顯示質因數分解與計算式，不僅能查出答案之誤，也能查出推導之誤。

理解 RSA 加密的原理

RSA 以兩個質數 p、q 之積 n = pq 作為公鑰，而產生私鑰則需要 φ(n) = (p−1)(q−1)。用小質數實際算一遍，便能具體把握這一關係。

驗證歐拉定理

對與 n 互質的 a，a^φ(n) 除以 n 的餘數為1，這便是歐拉定理。先求出 φ(n)，即可用小數值實際試驗其成立。

觀察積性函數的性質

當 m 與 n 互質時，φ(mn) = φ(m)φ(n) 成立。把速查表中的值組合起來，即可確認此性質確實成立。

想查質因數分解本身時

若只需分解的結果，請使用質因數分解；若要判定是否為質數，請使用質數判定。

與歐拉函數相關的用語

歐拉函數（totient 函數）: 指回傳1到 n 的整數中與 n 互質者個數的函數。記作 φ(n)，由18世紀的萊昂哈德·歐拉引入。
互質: 指兩個整數的最大公因數為1的狀態，與「不含任何共同質因數」同義。
質因數分解: 指把整數寫成質數之積的形式。因 φ(n) 僅由 n 的相異質因數決定，故此分解即為計算的起點。
積性函數: 指對互質的 m 與 n 滿足 f(mn) = f(m)f(n) 的函數。φ 具有此性質，這也正是可把大數的 φ 按質因數分開求得的緣由。
歐拉定理: 指對與 n 互質的整數 a，a 的 φ(n) 次方除以 n 的餘數必為1的定理。限定於質數的情形即為費馬小定理。
RSA 加密: 指以兩個大質數之積作為公鑰的公開金鑰加密。私鑰的計算需要 φ(n)，而若無法把 n 質因數分解便無從求得 φ(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加密安全性的基礎之一。

檢視全部趣味知識