오일러 피 함수

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

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

정의

양의 정수 $n$의 오일러 피 함수 $\varphi (n)$은 정수환의 몫환 $\mathbb{Z}/(n)$의 가역원군의 원소 개수이다. 즉, 1부터 $n$까지의 정수 가운데 $n$과 서로소인 것들의 개수이다.

$\varphi (n)=|(\mathbb{Z}/(n){)}^{\times }|=|\{k\in \{1,\dots ,n\}:\gcd \{n,k\}=1\}|$

성질

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

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

오일러 피 함수 값은 소인수를 통해 다음과 같이 구할 수 있다. 이를 오일러 곱 공식(틀:Llang)이라고 한다.

$\varphi (n)=n\prod _{p\mid n}(1-\frac{1}{p})$

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

$\varphi (20)=20(1-\frac{1}{2})(1-\frac{1}{5})=20\times \frac{1}{2}\times \frac{4}{5}=8$

특히, 소수 $p$의 거듭제곱 $p^k$의 오일러 피 함수 값은

$\varphi (p^k)=p^{k-1}(p-1)$

이며, 소수 $p$의 값은

$\varphi (p)=p-1$

이다.

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

$\sum _{d|n}\varphi (d)=n$

이는 분수 $1/n,2/n,\dots ,n/n$들을 기약 분수 형태의 분모에 따라 묶어서 센 것으로 볼 수 있다. 이에 뫼비우스 반전 공식을 가하면

$\sum _{d|n}d\mu (n/d)=\varphi (n)$

을 얻는다 ($\mu$는 뫼비우스 함수).

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

$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

값

1부터 80까지의 정수의 오일러 피 함수 값은 다음과 같다. 틀:OEIS

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

응용

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

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

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

이라면

$\varphi (n)$ = 1, 2, 2, 4, 2, 4, 4, …

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

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

같이 보기

• 페르마의 소정리
• 조르당 피 함수
• 카마이클 피 함수
• 토션트 합 함수

외부 링크

• 틀:Eom
• 틀:매스월드