오일러 피 함수 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:EulerPhi.svg|섬네일|오일러 피 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다.]]

[[수론]]에서 '''오일러 피 함수'''(-函數, {{llang|en|Euler’s phi (totient) function}})는 [[정수환]]의 [[몫환]]의 [[가역원]]을 세는 [[함수]]이다. 즉, ''n''이 [[양의 정수]]일 때, ϕ(''n'')은 ''n''과 [[서로소 (수론)|서로소]]인 1부터 ''n''까지의 정수의 개수와 같다. 예를 들어, 1부터 6까지의 정수 가운데 1, 5 둘만 6과 서로소이므로, ϕ(6) = 2이다. 1부터 10까지의 정수는 모두 11과 서로소이며, 11은 자기 자신과 서로소가 아니므로, ϕ(11) = 10이다. 1은 자기 자신과 서로소이므로, ϕ(1) = 1이다.

== 정의 ==
양의 정수 <math>n</math>의 '''오일러 피 함수''' <math>\phi(n)</math>은 [[정수환]]의 [[몫환]] <math>\mathbb Z/(n)</math>의 [[가역원군]]의 원소 개수이다. 즉, 1부터 <math>n</math>까지의 정수 가운데 <math>n</math>과 [[서로소 아이디얼|서로소]]인 것들의 개수이다.
:<math>\phi(n)=|(\mathbb Z/(n))^\times|=|\{k\in\{1,\dotsc,n\}\colon\gcd\{n,k\}=1\}|</math>

== 성질 ==
오일러 피 함수는 [[곱셈적 함수]]다. 즉, 만약 두 정수 <math>m,n</math>이 서로소라면, 다음이 성립한다.
:<math>\phi(mn)=\phi(m)\phi(n)</math>

오일러 피 함수 값은 [[소인수]]를 통해 다음과 같이 구할 수 있다. 이를 '''오일러 곱 공식'''({{llang|en|Euler product formula}})이라고 한다.
:<math>\phi(n)=n\prod_{p\mid n} \left(1-\frac{1}{p}\right)</math>
예를 들어, 20의 소인수는 2, 5이므로 <math>\phi(20)</math>은 다음과 같이 구할 수 있다.
:<math>\phi(20)=20 \left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{5}\right)=20 \times \frac{1}{2} \times \frac{4}{5}=8</math>

특히, 소수 <math>p</math>의 거듭제곱 <math>p^k</math>의 오일러 피 함수 값은
:<math>\phi(p^k)=p^{k-1}(p-1)</math>
이며, 소수 <math>p</math>의 값은
:<math>\phi(p)=p-1</math>
이다.

오일러 피 함수를 통해 [[항등 함수]]를 다음과 같이 나타낼 수 있다. 이는 [[레온하르트 오일러]]가 증명하였다.
:<math>\sum_{d|n} \phi(d)=n</math>
이는 분수 <math>1/n,2/n,\dots,n/n</math>들을 기약 분수 형태의 분모에 따라 묶어서 센 것으로 볼 수 있다. 이에 [[뫼비우스 반전 공식]]을 가하면
:<math>\sum_{d|n}d\mu(n/d)=\phi(n)</math>
을 얻는다 (<math>\mu</math>는 [[뫼비우스 함수]]).

만약 양의 정수 <math>a,n</math>이 서로소라면, 다음과 같은 합동식이 성립한다. 이를 '''[[오일러의 정리]]'''라고 한다.
:<math>a^{\phi(n)}\equiv 1\pmod n</math>

== 값 ==
1부터 80까지의 정수의 오일러 피 함수 값은 다음과 같다. {{OEIS|A000010}}

{| class="wikitable"
! ''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
|}

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

또한, [[정다각형|정''n''각형]]이 [[작도 가능한 다각형]]인지, 즉 [[컴퍼스와 자 작도|눈금없는 자와 컴퍼스]]만으로 작도할 수 있는지는 <math>\phi(n)</math>이 2의 [[거듭제곱]]수인지와 [[동치]]이다. 즉,
:''n'' = 2, 3, 4, 5, 6, 8, 10, …
이라면
:<math>\phi(n)</math> = 1, 2, 2, 4, 2, 4, 4, …
이므로 정''n''각형을 작도할 수 있지만, 다른 값의 경우에는 작도할 수 없다. 특히, ''n''이 [[소수 (수론)|소수]]인 경우를 [[페르마 소수]]라고 한다.

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

== 같이 보기 ==
* [[페르마의 소정리]]
* [[조르당 피 함수]]
* [[카마이클 피 함수]]
* [[토션트 합 함수]]

== 외부 링크 ==
* {{eom|title=Totient function}}
* {{매스월드|id=TotientFunction|title=Totient function}}

[[분류:수론]]
[[분류:레온하르트 오일러]]
[[분류:모듈러 산술]]