오일러 피 함수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
오일러 φ 함수의 그래프. φ(1)부터 φ(1000)까지의 값들을 나타낸다.

정수론에서, 오일러 φ 함수(Euler φ 函數, 영어: Euler’s phi (totient) function)는 1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수를 나타내는 함수이다. 양의 정수 n에 대하여 정의되며, 함수로는, 일반적으로 φ(n)으로 표기한다.

예시[편집]

  • 1, 2, 3, 4, 5, 6 중에, 6과 서로소인 수는 1, 5 두 개이다. 따라서, φ(6) = 2
  • 1, 2, 3, 4, 5, 6, 7 중에, 7 이외에는 모두 7과 서로소이다. 따라서, φ(7) =6
  • 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 중에, 11은 소수이다. 그러므로 11-1=10 따라서, φ(11)=10이다.

성질[편집]

소수 p의 경우 오일러 피 함수의 값은

\varphi(p)=p-1

이다. 일반적으로, \varphi곱셈적 함수다. 즉, m, n서로소인 정수일 때,

\varphi(mn)=\varphi(m)\varphi(n)

이다.

임의의 수의 약수들의 피 함수값들의 합은 원래 수와 같다. 이 공식은 레온하르트 오일러가 증명하였다.

\sum_{d|n} \varphi(d)=n

만약 an이 서로소이고 n이 자연수이면 다음이 성립한다. 이를 오일러의 정리라고 한다.

a^{\phi(n)}=1\pmod n

만약 어떤 수의 소인수들을 안다면, 그 오일러 피 함수는 다음과 같이 계산할 수 있다. 이 공식을 오일러 곱 공식(영어: Euler product formula)이라고 한다.

\varphi(n) = n \prod_{p | n }(1-1/p)

응용[편집]

오일러 피 함수는 수학의 다양한 분야에서 등장한다. 예를 들어, 군론에서는 순환군 \mathbb Z/n\mathbb Z의 가능한 생성원(generator)의 수는 \phi(n)이다. 이는 n과 서로소인 임의의 수를 사용하여 \mathbb Z/n\mathbb Z를 생성할 수 있기 때문이다.

또한, 정n각형이 작도 가능한 다각형인지, 즉 눈금없는 자와 컴퍼스만으로 작도할 수 있는지는 \phi(n)이 2의 거듭제곱수인지와 동치이다. 즉,

n = 2, 3, 4, 5, 6, 8, 10, …

이라면

\phi(n) = 1, 2, 2, 4, 2, 8, 4, …

이므로 정n각형을 작도할 수 있지만, 다른 값의 경우에는 작도할 수 없다. 특히, n소수인 경우를 페르마 소수라고 한다.

오일러 피 함수는 암호학RSA 암호에서도 핵심적인 역할을 한다.

[편집]

1부터 80까지의 오일러 피 함수 값은 다음과 같다. (OEIS의 수열 A000010)

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

관련 항목[편집]