오일러 피 함수

수론에서 오일러 파이 함수(-函數, 영어: 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이다.

오일러 파이 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다.

정의 편집

양의 정수  오일러 파이 함수  정수환몫환  가역원군의 원소 개수이다. 즉, 1부터  까지의 정수 가운데  서로소인 것들의 개수이다.

 

성질 편집

편집

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

항등식 편집

오일러 파이 함수는 곱셈적 함수다. 즉, 만약 두 정수  이 서로소라면, 다음이 성립한다.

 


오일러 파이 함수 값은 소인수를 통해 다음과 같이 구할 수 있다. 이를 오일러 곱 공식(영어: Euler product formula)이라고 한다.

 

예를 들어, 20의 소인수는 2, 5이므로  은 다음과 같이 구할 수 있다.

 


그리고, 소수  의 거듭제곱  의 오일러 파이 함수 값은

 

이다. 특히 소수  의 경우

 

이다.


오일러 파이 함수를 통해 항등 함수를 다음과 같이 나타낼 수 있다. 이는 레온하르트 오일러가 증명하였다.

 

또한, 다음이 성립한다.

 

여기서  뫼비우스 함수이다.


만약 양의 정수  이 서로소라면, 다음과 같은 합동식이 성립한다. 이를 오일러의 정리라고 한다.

 

응용 편집

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

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

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

이라면

  = 1, 2, 2, 4, 2, 4, 4, …

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

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

같이 보기 편집

외부 링크 편집