오일러 피 함수

오일러 φ 함수(Euler's phi 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이다.

계산법

n을 소인수분해한 것이 다음과 같다고 하자. 단, p_k는 서로 다른 소수를 나타낸다.

$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)개 존재한다.
• a와 n이 서로소이고 n이 자연수이면 $a^{\phi(n)}=1$(mod n) (이를 오일러의 정리라고 한다.)

함수값 표

1부터 80까지의 오일러 파이 함수 값은 다음과 같다.

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$\varphi(n)$	1	1	2	2	2	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
$\varphi(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
$\varphi(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
$\varphi(n)$	60	30	36	32	48	20	66	32	44	24	70	24	72	36	40	36	60	24	78	32

관련 항목

• 레온하르트 오일러
• 대수학
• 수론
• 페르마의 소정리