오일러 파이 함수
위키백과 ― 우리 모두의 백과사전.
오일러 φ 함수 (Euler's Phi function) 는 양의 정수 n에 정의되는 함수로, 일반적으로 φ(n) 로 표기한다. 1부터 n까지의 양의 정수 중에 n과 서로소인 것의 갯수를 나타내는 함수이다.
목차 |
[편집] 예
- 1,2,3,4,5,6 중에, 6과 서로 소인 수는 1, 5 두개이다. 따라서, φ(6) = 2
- 1,2,3,4,5,6,7 중에, 7이외에는 모두 7과 서로 소이다. 따라서, φ(7) = 6
[편집] 계산법
n을 소인수 분해한 것이 다음과 같다고 하자. 단, pk는 서로 다른 소수를 나타낸다.
이 때, φ(n)는 다음과 같이 계산할 수 있다.
[편집] 성질
- p가 소수일 때, φ(p) = p - 1
- m,n 가 서로 소인 정수일 때, φ(mn) = φ(m)φ(n) (곱셈적 함수)
- 잉여환 Z/mZ 으로 이루어진 군의 위수는 φ(m)이다.
- G 를 위수 n인 순환군이라 하자. n의 약수 r에 대해, 위수가 r인 G의 원소는 φ(r) 개 존재한다.
- 특히, 순환군 G 의 생성원은 φ(n)개 존재한다.
[편집] 함수값 표
1부터 80까지의 오일러 파이 함수 값은 다음과 같다.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 | 8 |
| n | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| φ(n) | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 | 16 |
| n | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| φ(n) | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 | 16 |
| n | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| φ(n) | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 | 32 |
