오일러 정리 (영어 : Euler’s theorem )는 수론 의 하나로, 페르마의 소정리 를 일반화한 정리의 하나이다.
정수
a
{\displaystyle a}
n
{\displaystyle n}
a
{\displaystyle a}
n
{\displaystyle n}
서로소 라고 하자. 오일러 정리 에 따르면,
a
ϕ
(
n
)
{\displaystyle a^{\phi (n)}}
n
{\displaystyle n}
합동 이다.
a
ϕ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}}
군론을 통한 증명 [ 편집 ] 정수환 의 몫환
Z
/
(
n
)
{\displaystyle \mathbb {Z} /(n)}
가역원군
(
Z
/
(
n
)
)
×
{\displaystyle (\mathbb {Z} /(n))^{\times }}
ord
a
{\displaystyle \operatorname {ord} a}
a
{\displaystyle a}
(
Z
/
(
n
)
)
×
{\displaystyle (\mathbb {Z} /(n))^{\times }}
라그랑주 정리 에 따라,
ord
a
{\displaystyle \operatorname {ord} a}
ϕ
(
n
)
{\displaystyle \phi (n)}
ϕ
(
n
)
=
k
ord
a
{\displaystyle \phi (n)=k\operatorname {ord} a}
인 양의 정수
k
{\displaystyle k}
a
ϕ
(
n
)
=
a
k
ord
a
=
(
a
ord
a
)
k
≡
1
k
=
1
(
mod
n
)
{\displaystyle a^{\phi (n)}=a^{k\operatorname {ord} a}=(a^{\operatorname {ord} a})^{k}\equiv 1^{k}=1{\pmod {n}}}
이다.
군론을 사용하지 않는 증명 [ 편집 ] 정수의 집합
{
x
1
,
x
2
,
…
,
x
m
}
{\displaystyle \{x_{1},x_{2},\dots ,x_{m}\}}
㈀ 만약
i
≠
j
{\displaystyle i\neq j}
x
i
≢
x
j
(
mod
n
)
{\displaystyle x_{i}\not \equiv x_{j}{\pmod {n}}}
㈁ 각
i
{\displaystyle i}
x
i
{\displaystyle x_{i}}
n
{\displaystyle n}
㈂ 만약
x
{\displaystyle x}
n
{\displaystyle n}
x
=
x
i
(
mod
n
)
{\displaystyle x=x_{i}{\pmod {n}}}
i
{\displaystyle i}
㈃
m
=
ϕ
(
n
)
{\displaystyle m=\phi (n)}
위 네 조건을 만족시키는 정수 집합은 반드시 존재한다. 예를 들어
{
0
,
1
,
2
,
…
,
n
−
1
}
{\displaystyle \{0,1,2,\dots ,n-1\}}
n
{\displaystyle n}
{
x
1
,
x
2
,
…
,
x
ϕ
(
n
)
}
{\displaystyle \{x_{1},x_{2},\dots ,x_{\phi (n)}\}}
r
i
∈
{
0
,
1
,
2
,
…
,
n
−
1
}
{\displaystyle r_{i}\in \{0,1,2,\dots ,n-1\}}
x
i
{\displaystyle x_{i}}
n
{\displaystyle n}
{
r
1
,
r
2
,
…
,
r
ϕ
(
n
)
}
{\displaystyle \{r_{1},r_{2},\dots ,r_{\phi (n)}\}}
ϕ
{\displaystyle \phi }
{
0
,
1
,
2
,
…
,
n
−
1
}
{\displaystyle \{0,1,2,\dots ,n-1\}}
n
{\displaystyle n}
x
{\displaystyle x}
n
{\displaystyle n}
x
{\displaystyle x}
n
{\displaystyle n}
r
i
{\displaystyle r_{i}}
위 네 조건을 만족시키는 정수 집합
{
x
1
,
x
2
,
…
,
x
ϕ
(
n
)
}
{\displaystyle \{x_{1},x_{2},\dots ,x_{\phi (n)}\}}
{
a
x
1
,
a
x
2
,
…
,
a
x
ϕ
(
n
)
}
{\displaystyle \{ax_{1},ax_{2},\dots ,ax_{\phi (n)}\}}
조건 ㈀.
a
x
i
≡
a
x
j
(
mod
n
)
{\displaystyle ax_{i}\equiv ax_{j}{\pmod {n}}}
n
{\displaystyle n}
a
(
x
i
−
x
j
)
{\displaystyle a(x_{i}-x_{j})}
n
{\displaystyle n}
a
(
x
i
−
x
j
)
{\displaystyle a(x_{i}-x_{j})}
a
{\displaystyle a}
n
{\displaystyle n}
a
{\displaystyle a}
n
{\displaystyle n}
n
{\displaystyle n}
x
i
−
x
j
{\displaystyle x_{i}-x_{j}}
n
{\displaystyle n}
x
i
−
x
j
{\displaystyle x_{i}-x_{j}}
x
i
≡
x
j
{\displaystyle x_{i}\equiv x_{j}}
i
=
j
{\displaystyle i=j}
조건 ㈁.
a
{\displaystyle a}
x
i
{\displaystyle x_{i}}
n
{\displaystyle n}
a
x
i
{\displaystyle ax_{i}}
n
{\displaystyle n}
조건 ㈃. 첫 번째 조건에 따라
a
x
i
{\displaystyle ax_{i}}
이제,
{
a
x
1
,
a
x
2
,
…
,
a
x
ϕ
(
n
)
}
{\displaystyle \{ax_{1},ax_{2},\dots ,ax_{\phi (n)}\}}
{
x
1
,
x
2
,
…
,
x
ϕ
(
n
)
}
{\displaystyle \{x_{1},x_{2},\dots ,x_{\phi (n)}\}}
i
∈
{
1
,
2
,
…
,
ϕ
(
n
)
}
{\displaystyle i\in \{1,2,\dots ,\phi (n)\}}
x
i
≡
a
x
σ
(
i
)
(
mod
n
)
{\displaystyle x_{i}\equiv ax_{\sigma (i)}{\pmod {n}}}
인
σ
(
i
)
∈
{
1
,
2
,
…
,
ϕ
(
n
)
}
{\displaystyle \sigma (i)\in \{1,2,\dots ,\phi (n)\}}
x
i
{\displaystyle x_{i}}
a
x
σ
(
i
)
{\displaystyle ax_{\sigma (i)}}
σ
(
i
)
{\displaystyle \sigma (i)}
σ
:
{
1
,
2
,
…
,
ϕ
(
n
)
}
→
{
1
,
2
,
…
,
ϕ
(
n
)
}
{\displaystyle \sigma \colon \{1,2,\dots ,\phi (n)\}\to \{1,2,\dots ,\phi (n)\}}
a
ϕ
(
n
)
∏
i
=
1
n
x
i
=
∏
i
=
1
n
a
x
σ
(
i
)
≡
∏
i
=
1
n
x
i
(
mod
n
)
{\displaystyle a^{\phi (n)}\prod _{i=1}^{n}x_{i}=\prod _{i=1}^{n}ax_{\sigma (i)}\equiv \prod _{i=1}^{n}x_{i}{\pmod {n}}}
이며,
∏
i
=
1
n
x
i
{\displaystyle \textstyle \prod _{i=1}^{n}x_{i}}
n
{\displaystyle n}
a
ϕ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}}
이다.
페르마의 소정리 [ 편집 ] 페르마의 소정리 는 오일러 정리의 특수한 경우이다. 정수
a
{\displaystyle a}
소수
p
{\displaystyle p}
p
{\displaystyle p}
a
{\displaystyle a}
a
{\displaystyle a}
p
{\displaystyle p}
1
,
2
,
…
,
p
−
1
{\displaystyle 1,2,\dots ,p-1}
p
{\displaystyle p}
ϕ
(
p
)
=
p
−
1
{\displaystyle \phi (p)=p-1}
이다. 따라서
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}
이다.
오일러 피 함숫값의 홀짝성 [ 편집 ] 양의 정수
n
≥
3
{\displaystyle n\geq 3}
n
{\displaystyle n}
(
−
1
)
ϕ
(
n
)
≡
1
(
mod
n
)
{\displaystyle (-1)^{\phi (n)}\equiv 1{\pmod {n}}}
이다. 즉,
ϕ
(
n
)
{\displaystyle \phi (n)}
스위스 의 수학자 레온하르트 오일러 가 증명하였다.
같이 보기 [ 편집 ] 
기하학 정리에 대해서는 오일러 삼각형 정리 문서를 참고하십시오.
이 부분의 본문은 페르마의 소정리입니다.
