군론을 통한 증명
편집
정수환 의 몫환
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}}}
이다.
기하학 정리에 대해서는 오일러 삼각형 정리 문서를 참고하십시오.
이 부분의 본문은 페르마의 소정리입니다.
