오일러 피 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다. 수론 에서 오일러 피 함수 (-函數, 영어 : 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이다.
양의 정수
n
{\displaystyle n}
오일러 피 함수
ϕ ϕ -->
(
n
)
{\displaystyle \phi (n)}
정수환 의 몫환
Z
/
(
n
)
{\displaystyle \mathbb {Z} /(n)}
가역원군 의 원소 개수이다. 즉, 1부터
n
{\displaystyle n}
n
{\displaystyle n}
서로소 인 것들의 개수이다.
ϕ ϕ -->
(
n
)
=
|
(
Z
/
(
n
)
)
× × -->
|
=
|
{
k
∈ ∈ -->
{
1
,
… … -->
,
n
}
: : -->
gcd
{
n
,
k
}
=
1
}
|
{\displaystyle \phi (n)=|(\mathbb {Z} /(n))^{\times }|=|\{k\in \{1,\dotsc ,n\}\colon \gcd\{n,k\}=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
오일러 피 함수는 곱셈적 함수 다. 즉, 만약 두 정수
m
,
n
{\displaystyle m,n}
ϕ ϕ -->
(
m
n
)
=
ϕ ϕ -->
(
m
)
ϕ ϕ -->
(
n
)
{\displaystyle \phi (mn)=\phi (m)\phi (n)}
소인수 를 통해 다음과 같이 구할 수 있다. 이를 오일러 곱 공식 (영어 : Euler product formula )이라고 한다.
ϕ ϕ -->
(
n
)
=
n
∏ ∏ -->
p
∣ ∣ -->
n
(
1
− − -->
1
p
)
{\displaystyle \phi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}
예를 들어, 20의 소인수는 2, 5이므로
ϕ ϕ -->
(
20
)
{\displaystyle \phi (20)}
ϕ ϕ -->
(
20
)
=
20
(
1
− − -->
1
2
)
(
1
− − -->
1
5
)
=
20
× × -->
1
2
× × -->
4
5
=
8
{\displaystyle \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}
p
{\displaystyle p}
p
k
{\displaystyle p^{k}}
ϕ ϕ -->
(
p
k
)
=
p
k
− − -->
1
(
p
− − -->
1
)
{\displaystyle \phi (p^{k})=p^{k-1}(p-1)}
이다. 특히 소수
p
{\displaystyle p}
ϕ ϕ -->
(
p
)
=
p
− − -->
1
{\displaystyle \phi (p)=p-1}
이다.
항등 함수 를 다음과 같이 나타낼 수 있다. 이는 레온하르트 오일러 가 증명하였다.
∑ ∑ -->
d
|
n
ϕ ϕ -->
(
d
)
=
n
{\displaystyle \sum _{d|n}\phi (d)=n}
또한, 다음이 성립한다.
∑ ∑ -->
d
|
n
d
μ μ -->
(
n
/
d
)
=
ϕ ϕ -->
(
n
)
{\displaystyle \sum _{d|n}d\mu (n/d)=\phi (n)}
여기서
μ μ -->
{\displaystyle \mu }
뫼비우스 함수 이다.
a
,
n
{\displaystyle a,n}
오일러의 정리 라고 한다.
a
ϕ ϕ -->
(
n
)
≡ ≡ -->
1
(
mod
n
)
{\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}}
오일러 피 함수는 수학의 다양한 분야에서 등장한다. 예를 들어, 군론 에서는 순환군
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
ϕ ϕ -->
(
n
)
{\displaystyle \phi (n)}
n
{\displaystyle n}
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
또한, 정n 각형 이 작도 가능한 다각형 인지, 즉 눈금없는 자와 컴퍼스 만으로 작도할 수 있는지는
ϕ ϕ -->
(
n
)
{\displaystyle \phi (n)}
거듭제곱 수인지와 동치 이다. 즉,
n = 2, 3, 4, 5, 6, 8, 10, …이라면
ϕ ϕ -->
(
n
)
{\displaystyle \phi (n)}
이므로 정n 각형을 작도할 수 있지만, 다른 값의 경우에는 작도할 수 없다. 특히, n 이 소수 인 경우를 페르마 소수 라고 한다.
오일러 피 함수는 암호학 의 RSA 암호 에서도 핵심적인 역할을 한다.
