오일러 파이 함수

위키백과 ― 우리 모두의 백과사전.

오일러 φ 함수 (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 = \prod_{k=1}^d {p_k}^{e_k}

이 때, φ(n)는 다음과 같이 계산할 수 있다.


\varphi(n) = n \prod_{k=1}^d \left(1-\frac{1}{p_k}\right)

[편집] 성질

  • p가 소수일 때, φ(p) = p - 1
  • m,n 가 서로 소인 정수일 때, φ(mn) = φ(m)φ(n) (곱셈적 함수)
  • \sum_{d|n} \varphi(d) = n \qquad \frac{}{}
  • 잉여환 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

[편집] 관련 항목