오일러 파이 함수(φ, 토션트 함수) 계산기
정수 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이 됩니다. 소수와 서로소인 수는 그 소수 자신을 제외한 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과 자기 자신 외에는 약수를 갖지 않으므로, 1부터 p까지의 정수 중 p를 제외한 모든 수가 p와 서로소입니다. 따라서 φ(p) = p − 1이 됩니다.
RSA 암호는 두 개의 큰 소수 p, q를 곱한 합성수 n = pq를 공개키의 일부로 사용합니다. 비밀키를 계산하려면 φ(n) = (p−1)(q−1) 값이 필요한데, n을 소인수분해하지 못하면 φ(n)을 구할 수 없기 때문에 큰 수의 소인수분해가 어렵다는 점이 RSA 암호 안전성의 토대가 됩니다.
여담 ― 18세기 오일러가 발견한 「서로소」를 세는 함수
오일러 파이 함수(토션트 함수)는 18세기 스위스 수학자 레온하르트 오일러가 1763년경 도입한 것으로 알려져 있습니다. 처음에는 페르마의 소정리를 합성수로 일반화하는 과정에서 연구되었으며, 현재 사용되는 기호 φ(파이)는 이후 다른 수학자들이 표기법을 정리하면서 정착되었습니다.
얼핏 단순해 보이는 「서로소인 수를 세는」 연산이지만, φ(n)에는 몇 가지 아름다운 성질이 있습니다. 예를 들어 n의 모든 약수 d에 대해 φ(d)를 더하면 반드시 n 자신과 일치합니다(Σφ(d) = n). 이는 초등 정수론의 기본 항등식 중 하나입니다.
오늘날 φ(n)은 RSA 암호의 키 생성에 필수적인 역할을 합니다. RSA 암호는 두 개의 큰 소수 p, q의 곱 n = pq를 공개키의 일부로 사용하는데, 비밀키를 만들 때 φ(n) = (p−1)(q−1) 값이 필요합니다. n을 소인수분해하지 않고는 φ(n)을 계산할 수 없다는 사실(적어도 현재 알려진 알고리즘으로는)이 RSA 암호 안전성의 근거 중 하나입니다.