페르마의 작은 정리 증명서

이 글은 페르마의 작은 정리에 대한 다양한 증거들을 한데 모아, 다음과 같이 기술하고 있다.

${\displaystyle a^{p}\equiv a{\pmod{p}}}$

모든 소수 p와 모든 정수에 대해 (모듈식 산술 참조)

단순화

아래에 제시된 페르마의 작은 정리에 대한 증명들 중 일부는 두 가지 단순화에 의존한다.

첫째는 a가 0 ≤ a p - 1 범위에 있다고 가정할 수 있다는 것이다.이것은 모듈식 산술의 법칙의 간단한 결과일 뿐이다; 우리는 단지 우리가 먼저 modulo p를 줄일 수 있다고 말하고 있다.이는 확인할 수 있듯이 ${\$ a$^{p}$모듈로$$ $p$를 줄이는 것과 일치한다.

둘째로, 그것은 증명하기에 충분하다.

${\displaystyle a^{p-1}\equiv 1{\pmod{p}}}$

a의 경우 1 ≤ a 1 p - 1의 범위에 있다.실제로, 이전의 주장이 그러한 것을 고수한다면, 양쪽을 곱하여 정리의 원래 형태를 산출한다.

${\displaystyle a^{p}\equiv a{\pmod{p}}}$

반면 a = 0 또는 a = 1이면 정리는 사소한 것으로 잡는다.

콤비네이터

목걸이를 세어 증명

이것은 아마도 가장 간단한 것으로 알려진 증거일 것이며, 최소한의 수학적 배경을 필요로 한다.그것은 결합 증명(두 가지 다른 방법으로 물체의 컬렉션을 세는 것을 포함하는 증거)의 매력적인 예다.

여기에 제시된 증거는 골롬의 증거를 각색한 것이다.^[1]

단순하게 하기 위해 a는 양의 정수라고 가정해 보자.다른 기호를 가진 알파벳을 사용하여 가능한 모든 p 기호의 문자열을 고려하십시오.각 p 포지션에 대한^p 가능성이 있기 때문에(제품 규칙 참조) 이러한 문자열의 총 수는 a이다.

예를 들어 p = 5와 a = 2인 경우, 두 개의 기호(예: A와 B)가 있는 알파벳을 사용할 수 있으며, 길이⁵ 5의 2 = 32개의 문자열이 있다.

AAAAAA, AAAAB, AAABA, AAABB, AABAA, AABAB, AABB,

아바아, 아바바, 아바바, 아바바, 아바바, 아바바, 아바바, 아바바, 아바바, 아바바, 아바바, 아바바, 아바비,

BAAAA, BAAAB, BABAB, BABAA, BABAB, BABB, BABB,

BBAAA, BBAAB, BBBA, BBAB, BBBAA, BBBAB, BBBB.

아래에서는 단일 기호로 구성된 문자열을 목록에서 제거하면(우리의 예에서는 AAAAA와 BBBBBB), 나머지^p a - 문자열을 그룹별로 배열할 수 있다고 주장할 것이다.따라서^p a - a는 p로 나누어진다.

목걸이

목걸이를 나타내는 것과 같은 각각의 끈을 생각해 봅시다.즉, 현악의 양쪽 끝을 서로 연결하고, 한 줄을 돌려서 두 번째 현을 얻을 수 있다면 두 줄을 같은 목걸이로 간주하는 것이다. 이 경우에는 두 현이 친구라고 말할 것이다.이 예에서 다음 문자열은 모두 친구들이다.

AAAAB, AAABA, AAAA, ABAA, ABAA, BAAAA.

전체적으로 다음 목록의 각 줄은 목걸이 하나에 해당하며, 전체 목록은 32개의 문자열로 구성된다.

AAAAB, AAABA, AAAA, ABAA, ABAA, BAAA,

AAABB, AABBA, ABBAA, BBAAA, BAAAB, BAAB,

AABAB, ABABA, BBAAA, ABAABAB, BABA,

AABBB, ABBA, BBBA, BBAAB, BABB, BABB,

아바브, 바바, 아바, 아바바, 비비바, 바밥,

ABBBB, BBBA, BBBB, BBB, BBB, BBBBBB,

AAAAA,

BBBBB.

위의 목록에서 둘 이상의 기호가 있는 각 목걸이는 5개의 다른 현으로 표시되며, 한 개의 현으로 표시된 목걸이의 수는 2개, 즉 구별되는 기호의 수입니다.따라서 이 목록은 32 - 2가 5로 구분되는 이유를 매우 명확하게 보여준다.

다음 규칙을 사용하여 주어진 문자열 S가 얼마나 많은 친구를 가지고 있는지 알아낼 수 있다.

만약 S가 여러 개의 문자열 T로 이루어져 있고, T 자체가 더 이상 반복 문자열로 분해될 수 없다면, S의 친구 수(S자체 포함)는 T의 길이와 같다.

예를 들어, 짧은 문자열 T = ABB의 여러 복사본으로 구성된 S = ABBBAB로 시작한다고 가정합시다.한 번에 하나의 기호를 회전시키면 다음과 같은 3개의 문자열을 얻게 된다.

abbabbabbabb,

비비밥ABBA,

밥밥BBAB.

ABB는 정확히 3개의 상징이고 더 이상 반복되는 문자열로 나눌 수 없기 때문에 다른 것은 없다.

증명서 작성

위의 규칙을 이용하여 페르마의 작은 정리에 대한 증거를 다음과 같이 꽤 쉽게 완성할 수 있다.문자열의 ^p 시작 풀은 두 가지 범주로 나눌 수 있다.

• 일부 문자열에는 p와 동일한 기호가 있다.알파벳의 각 기호마다 하나씩 정확히 이것들 중 하나가 있다.(우리의 실행 예에서, 이것들은 AAAAAA와 BBBBB의 문자열이다.
• 나머지 문자열은 알파벳에서 적어도 두 개의 구별되는 기호를 사용한다.만약 우리가 S를 일부 문자열 T의 반복복사로 나눌 수 있다면, T의 길이는 S의 길이를 나누어야 한다.그러나 S의 길이가 prime p이기 때문에 T의 유일한 길이도 p이다.따라서 위의 규칙은 S에게 정확히 p 친구가 있다는 것을 말해준다(S자체 포함).

두 번째 범주는 a ^p - 줄을 포함하며, 각 목걸이에 대해 한 그룹씩 p 문자열 그룹으로 배열할 수 있다.따라서 ^p a - a는 약속대로 p로 분할해야 한다.

동적 시스템을 사용한 증명

이 증거는 역동적인 시스템에서 나온 몇 가지 기본 개념을 사용한다.^[2]

먼저 함수_n T(x)의 패밀리를 고려한다. 여기서 n ≥ 2는 정수이고, 그 간격은 공식으로 [0, 1]을 그 자체에 매핑한다.

${\displaystyle T_{n}(x)={\begin{case}\{nx\}&0\leq x<1,\1&x=1,\case}}}}$

여기서 {y}은(는) y의 일부분을 나타낸다.예를 들어, 기능₃ T(x)는 아래에 설명되어 있다.

숫자 x는₀ f(x₀) = x이면₀ 함수 f(x)의 고정점이고, 다시 말해 f가₀ x를 고정된 상태로 두면 함수 f(x)의 고정점이라고 한다.함수의 고정점은 쉽게 그래픽으로 찾을 수 있다: 단순히 f(x)의 그래프가 y = x 선 그래프와 교차하는 지점의 x 좌표일 뿐이다. 예를 들어, 함수₃ T(x)의 고정점은 0, 1/2 및 1이며, 다음 다이어그램에 블랙 원으로 표시된다.

우리는 다음의 두 개의 레마를 요구할 것이다.

보조정리 1.n ≥ 2의 경우, 함수 T_n(x)에는 정확히 고정점이 n개 있다.

증명. 위의 그림에는 3개의 고정된 점이 있으며, 동일한 종류의 기하학적 논거가 n 2 2에 적용된다.

보조정리 2.모든 양의 정수 n과 m과 0 ≤ x ≤ 1에 대해,

${\displaystyle T_{m}(T_{n}(x))=T_{mn}(x).}$

즉 T_mn(x)는 T_n(x)와 T_m(x)의 구성이다.

증명. 이 보조정리증의 증명은 어렵지 않지만, 엔드포인트 x = 1에 약간 주의해야 한다.이 점에 있어서, 보조마사는 분명히 진실이다.

${\displaystyle T_{m}(T_{n}(1)=T_{m}(1)=1=T_{mn}(1)}$

0 ≤ x < 1이라고 가정해 봅시다.이 경우,

${\displaystyle T_{n}(x)=\{nx\}<1,}$

그래서_m T(T_n)(x)는 다음에 의해 주어진다.

${\displaystyle T_{m}(T_{n}(x))=\{m\{nx\}\}.}$

그러므로 우리가 정말 보여줘야 할 것은 바로는 것이다.

${\displaystyle \{m\{nx\}\}=\{mnx\}.}$

이를 위해 {nx} = nx - k를 관찰하며, 여기서 k는 nx의 정수 부분이고, 그 다음

${\displaystyle \{m\{nx\}\}=\{mnx-mk\}=\{mnx\}}}$

mk는 정수니까.

이제 기능 T_a^p(x)를 연구함으로써 페르마의 작은 정리에 대한 증거를 제대로 시작해보자.우리는 2파운드라고 가정할 것이다.Lemma 1로부터, 우리는 그것이^p 고정된 포인트를 가지고 있다는 것을 안다.Lemma 2에 의해 우리는 그것을 안다.

${\displaystyle T_{a^{p}}}=\underbrace {T_{a}(\cdots T_{a}(x)\cdots )}_{p{\text}}}}},}$

따라서_a T(x)의 고정점은 자동으로 T_a^p(x)의 고정점이다.

우리는_a T(x)의 고정점이 아닌 T_a^p(x)의 고정점에 관심이 있다.그러한 점들의 집합을 S라고 부르자.S에는 a^p - 포인트가 있는데, Lemma 1에 의해 T(x_a)는 정확히 고정 포인트가 있기 때문이다.다음 도표는 a = 3과 p = 2의 상황을 보여준다.검은 원은 S의 점이며, 그 중 3² - 3 = 6이 있다.

그 증거의 주요 아이디어는 이제 세트 S를_a T 아래의 궤도로 분할하는 것이다.이것은 우리가 S에서 점 x를₀ 선택하고, T(x_a)를 반복적으로 적용하여 점의 순서를 얻는다는 것을 의미한다.

${\displaystyle x_{0},T_{a}(x_{0}),T_{a}(T_{a}(x_{0}),T_{a}(T_{a}(T_{a}(x_{0}),\ldots .}$

이 시퀀스를 T 밑에_a x의₀ 궤도라고 한다. Lemema 2에 의해 이 시퀀스는 다음과 같이 다시 쓸 수 있다.

${\displaystyle x_{0},T_{a}(x_{0}),T_{a^{2}}(x_{0}),T_{a^{3}}(x_{0}),\ldots .}$

우리는₀ x가_{a ^p} T(x)의 고정점이라고 가정하고 있기 때문에, p step이 끝나면_a^p0 T(x₀) = x를 치고, 그 이후부터는 시퀀스가 스스로 반복된다.

그러나, 그 순서는 그보다 더 빨리 반복하기 시작할 수 없다.그렇다면 반복 구간의 길이는 p의 구분자여야 하므로 (p가 프라임이기 때문에) 1이어야 한다.그러나 이것은 x가₀ T의_a 고정점이 아니라는 우리의 가정과 모순된다.

즉, 궤도는 정확히 구별되는 점을 포함하고 있다.이것은 S의 모든 궤도를 지탱한다.따라서 a^p - 점을 포함하는 세트 S는 각각 p 점을 포함하는 궤도로 분할될 수 있으므로 a^p - a는 p에 의해 분할된다.

(이 증거는 위에서 주어진 목걸이 계산 증빙과 본질적으로 동일하며, 단순히 다른 렌즈를 통해 보는 것과 같다: 기본 a에 있는 자릿수 순서에 의해 주어진 간격[0, 1]을 생각할 수 있다(정수를 나타내는 우리의 구별은 ".0000"으로 끝나는 것으로 나타내는 익숙한 구별에 해당한다)."와 ".9999...").T는_aⁿ 그러한 시퀀스를 n자리수만큼 이동하는 양이다.이 점의 고정점은 주기가 n을 나누는 주기적인 시퀀스가 될 것이다.특히 T의_a^p 고정점은 길이 p의 목걸이로 생각할 수 있는데, T는_aⁿ 그러한 목걸이를 n개의 점으로 회전시키는 것에 해당한다.

또한 이 증거는 0과 1을 구분하지 않고 반개방 간격[0, 1)만 사용하여 제시될 수 있다. 그러면 T는_n n - 1 고정점만 가질 수 있지만 T_a^p - T는_a 필요에^p 따라 a - a로 해결된다.)

다항 교정쇄

이항 정리를 사용한 교정쇄

증명1길

이 증거는 오일러 때문에 유도를 사용하여 모든 정수 a ≥ 0에 대한 정리를 증명한다.^[3]

베이스 스텝, 즉 0^p mod 0 (mod p)은 사소한 것이다.다음으로 a = k에 대한 정리가 참이라면 a = k + 1에도 역시 참이라는 것을 보여줘야 한다. 이 귀납 단계를 위해서는 다음과 같은 보조마사가 필요하다.

보조정리. 모든 정수 x와 y와 prime p의 경우, (x + y)^p x x^p + y (mod^p p)

보조정리기는 신입생 꿈이 있는 경우다.나중에 증명할 것을 남겨두고 인덕션을 진행한다.

증명. k^p ≡ k (mod p)를 가정하고 (k+1)을 고려한다.^p보조정리해보니

${\displaystyle (k+1)^{p}^{p}\equiv k^{p}+1^{p}{\pmod {p}.}$

유도 가설을 사용하여 k^p ≡ k (mod p)를 얻는다; 그리고, 사소한 것으로는^p 1 = 1을 얻는다.그러므로,

${\displaystyle (k+1)^{p}\equiv k+1{\pmod{pmod},}$

a = k+1에 대한 정리의 문장이다.∎

보조정리법을 증명하기 위해서는 반드시 이항정리를 도입해야 하는데, 이항정리는 어떤 양의 정수 n에 대해서도,

${\displaystyle (x+y)^{n}=\sum _{i=0}^{n}{n \선택 i}x^{n-i}y^{i}}}}$

여기서 계수는 이항 계수,

${\displaystyle {n \선택 i}={\frac {n!}{i!(n-i)!}},}$

요인 함수의 측면에서 n! = 1×2×3×××n.

보조마 증거.지수가 prime p인 경우 이항 계수를 고려한다.

${\displaystyle {p \select i}={\frac {p!}{i!(p-i)!}}}$

이항 계수는 모두 정수다.분자에는 요인 p의 정의에 의한 인자가 들어 있다.0 < i < p>일 때 분모의 어느 항도 p의 인자(p의 원시성에 대한 반론)를 포함하지 않아 계수 자체가 분자로부터 p의 주요 인자를 소유하게 되어, 다음과 같이 암시한다.

${\displaystyle {p \select i}\equiv 0{\pmod{p},\qquad 0<i<p.}$

모둘로 p, 이것은 prime p. ∎의 이항정리 우측에 있는 합계의 첫 번째와 마지막을 제외한 모든 것을 제거한다.

p의 원시성은 보조정리에게 필수적이다; 그렇지 않으면, 우리는 다음과 같은 예들을 가지고 있다.

${\displaystyle {4 \선택 2}=6,}$

4로 나눌 수 없는.

증명2길

Lemma를 사용하면 다음과 같은 이점을 얻을 수 있다.

${\displaystyle k^{p}\equiv ((k-1)+1)^{p}\equiv (k-1)^{p}+1\equiv ((k-2)+1)^{p}+1\equiv (k-2)^{p}+2\equiv \dots \equiv k{\pmod {p}}}$.

다항 확장을 사용한 증명

레이브니즈(출판하지 않은 사람)^[4]가 먼저 발견하고 나중에 오일러가 재발견한 그 증거는 단순성을 위해 여기에 가져온 다항 정리의 매우 간단한 응용이다.^[3]

${\displaystyle(x_{1}+x_{2}+\cdots +x_{m})^{n}=\sum_{1}={k_{1}, k_{2},\ldots, k_{{m}}{n \cH00}, k_{m_{1}, k_{m_{1}^{k_{1}^{1},{1},{1},{1},{1},{1},{k_}}}}}.}$

합계는 모든 n의 음이 아닌 정수₁ 지수 k ~ k의_m 순서에 따라 계산된다. 따라서 모든 k의_i 합은 n이다.

따라서 1초(one)의 합으로 표현하면 우리는 얻는다.

${\displaystyle a^{p}=\sum _{k_{1},k_{2},\ldots,k_{a}{p}{p 선택 \k_{1}, k_{2},\ldots,k_{a}}}}}}$

분명히 p가 prime이고, k가_j j에 대해 p와 같지 않다면, 우리는

${\displaystyle {p \선택{1},k_{2},\ldots,k_{a}\equiv 0{\pmod{p}}}$

그리고

${\displaystyle {p \선택{1},k_{2},\ldots,k_{a}\equiv 1{\pmod{p}}}$

만약_j k가 어떤 j에 대해 p와 같다면.

정확히_j k = p와 같은 요소가 있기 때문에 정리가 뒤따른다.

(이 증거는 본질적으로 앞에서 주어진 목걸이 카운팅 증명의 동그라미 변종이다. 다항 계수는 임의의 아나그램으로 문자열을 허용할 수 있는 방법의 수를 카운트하는 반면, 목걸이 인수는 문자열을 순환 아나그램으로 회전시킬 수 있는 방법의 수를 카운트한다.즉, 여기서의 비종교 다항계수는 p에 의해 분할된다는 것은 길이 p의 각 비종교 목걸이를 여러 가지 방법으로 끈으로 풀 수 있다는 사실의 결과로 볼 수 있다.

물론 이 다항적 팽창은 위의 이항적 정리 기반 증거의 기초가 된다.)

전력 제품 확장을 사용한 입증

정식 전력 제품 확장에 기초한 적층 조합 증명서는 Gedrius Alkauskas에 의해 제공되었다.^[5]이 증명은 유클리드 알고리즘도 이항정리도 사용하지 않고 오히려 합리적인 계수를 갖는 형식적인 파워시리즈를 채용한다.

오일러 정리의 특별한 경우로서의 증거

제임스 아이보리에^[7] 의해 발견되고 디리클레에^[8] 의해 재발견된 ^[3][6]이 증거는 모듈식 산술의 어떤 배경을 필요로 한다.

p는 양성이며 a로 나누어지지 않는다고 가정해 보자.그 아이디어는 우리가 숫자의 순서를 적으면

${\displaystyle a,2a,3a,\ldots,(p-1)a}$

(A)

그리고 각각의 modulo p를 줄이면, 그 결과의 순서는

$1,2,3,\ldots,p-1.}$

(B)

따라서 각 시퀀스에서 숫자를 함께 곱하면 결과는 동일한 modulo p:

$\displaystyle a\a\pmod{pmod}\cdots \cdots \cdots \cdots \p-1a\cdiv 1\cdiv 2\cdives 3\cdots \cdots \p}{\pmod {p}.}$

약관을 종합하여 산출하다.

${\displaystyle a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p}.}$

마지막으로 이 방정식의 양쪽에서 1, 2, ..., p - 1을 "취소"할 수 있다.

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

위 증거에는 우리가 정당화할 필요가 있는 두 가지 단계가 있다.

• 수열의 요소(A), 감소된 modulo p가 (B)의 재배열인 이유 및
• 모듈식 산술 설정에서 "취소"가 유효한 이유.

우리는 아래의 것들을 증명할 것이다. 먼저 이 증거의 실례를 보자.

예

a = 3이고 p = 7이면 해당 순서는

$3,6,9,12,15,18;}$

modulo 7이 주는 감소

$3,6,2,5,1,4,}$

단지 의 재배열일 뿐이다.

${\displaystyle 1,2,3,4,5,6}$

그것들을 함께 곱하면

$3\displaystyle 3\cHB 6\buffer 12\buffer 15\buffer 18\buffer 3\buffer 1\buffer 1\buffer 1\buffer 3\buffer 4\buffer 5\buffer 6\pmod {7};};}$

그것은

${\displaystyle 3^{6}(1\pmx 2\buff 3\buff 4\buff 5\buff 6)\equiv(1\buff 3\buff 3\buff 5\buff 6){\pmod {7}.}$

1 × 2 × 3 × 4 × 5 × 6 수율 취소

${\displaystyle 3^{6}\equiv 1{\pmod{7}},}$

그것은 사례 a = 3과 p = 7에 대한 페르마의 작은 정리다.

취소법

먼저 특정 상황에서 "취소"하는 것이 유효한 이유를 설명합시다.정확한 진술은 다음과 같다.u, x, y가 정수이고, u가 소수 p로 나누어져 있지 않다면, 그리고 if

${\displaystyle ux\equiv uy{\pmod{p}},}$

(C)

그러면 우리는 당신을 얻기 위해 "유"라고" 할 수도 있다.

${\displaystyle x\equiv y{\pmod {p}.}$

(D)

숫자 1, 2, ..., p - 1은 확실히 p로 나눌 수 없기 때문에(사실 그것들은 p보다 작다) 페르마의 작은 정리에 대한 위의 증거에서 우리가 이 취소법을 사용한 것은 유효했다.

프라임 p가 ab(a와 b가 정수인 곳)를 나누면 p가 a나 b를 나누어야 한다는 유클리드 보조정리기를 이용하면 쉽게 취소법을 증명할 수 있다.실제로 주장(C)은 p가 ux - uy = u(x - y)를 나눈다는 것을 의미한다.p는 u를 나누지 않는 프라임이기 때문에 유클리드 보조정리기는 x - y를 대신 나누어야 한다는 것을 말해준다; 즉 (D)가 쥐고 있다.

취소법이 가지고 있는 조건이 상당히 엄격하다는 점에 유의해야 하며, 이는 페르마의 작은 정리가 p가 프라임이라고 요구하는 이유를 설명해 준다.예를 들어, 2×2 2 2×5 (모드 6)이지만, 2 ( 5 (모드 6)는 사실이 아니다.단, 다음과 같은 취소법의 일반화에는 u, x, y, z가 정수인 경우, u와 z가 비교적 프라임인 경우, u와 z는 정수로 되어 있다.

${\displaystyle ux\equiv uy{\pmod{z}},}$

그러면 우리는 당신을 얻기 위해 "유"라고" 할 수도 있다.

${\displaystyle x\equiv y{\pmod {z}}.}$

이것은 유클리드 보조기구의 일반화에 따른 것이다.

재배열 속성

마지막으로, 우리는 왜 그 순서가

${\displaystyle a,2a,3a,\ldots,(p-1)a}$

modulo p를 줄이면, 시퀀스의 재배열이 된다.

$1,2,3,\ldots,p-1.}$

우선, a, 2a, ..., (p - 1)a라는 용어는 0모듈로 p에 합치할 수 없다. 왜냐하면 k가 숫자 1, 2, ..., p - 1 중 하나라면 k는 p와 비교적 프라임이기 때문에, 유클리드 보조자는 ka가 p와 인자를 공유하지 않는다는 것을 알려주기 때문이다.따라서 최소한 우리는 모듈로 p를 줄일 때 숫자 a, 2a, ..., (p - 1)a가 1, 2, 3, ..., p - 1 중에서 반드시 발견되어야 한다는 것을 알고 있다.

더욱이 a, 2a, ..., (p - 1)a의 숫자는 모두 모듈로 p를 줄인 후에 구별되어야 한다.

${\displaystyle ka\equiv ma{\pmod{p},}$

여기서 k와 m은 1, 2, ..., p - 1 중 하나이고, 그러면 취소법에 의하면

${\displaystyle k\equiv m{\pmod {p}}.}$

k와 m은 모두 1과 p - 1 사이이므로 동일해야 한다.따라서 modulo p를 줄였을 때 a, 2a, ..., (p - 1)a라는 용어는 구별되어야 한다.요약하자면 p - 1 숫자 a, 2a, ..., (p - 1)a modulo p를 줄이면, 순서 1, 2, ..., p - 1의 구별되는 구성원을 얻는다.이 중 정확히 p - 1이 있기 때문에, 전자가 후자의 재배열일 가능성이 있다.

오일러의 정리 적용

이 방법은 또한 오일러의 정리를 증명하는 데 사용될 수 있는데, 1부터 p - 1까지의 숫자가 일부 m(필수적인 것은 아님) 이하의 숫자와 coprime으로 대체된다는 점에서 약간 변경될 수 있다.정리재산 및 취소법(위에서 언급한 일반화된 형태에 따라) 모두 여전히 만족하고 있어 활용할 수 있다.

예를 들어, m = 10이면 m보다 작은 숫자와 m을 가진 coprime은 1, 3, 7, 9이다.따라서 다음과 같은 이점을 얻을 수 있다.

$(displaystyle a\pmod {10})}$

그러므로

${\displaystyle {a^{\varphi (10)}}\equiv 1{\pmod {10}}.}$

오일러 기준의 귀납으로서 증명

집단 이론을 이용한 증명

표준증거

이 증거는^[9] 집단 이론의 가장 기본적인 요소들을 요구한다.

곱셈(taken modulo p)의 조작으로 설정된 G = {1, 2, …, p - 1}이(가) 그룹을 형성한다는 것을 인식하는 것이다.검증하기 위해 어느 정도의 노력이 필요한 유일한 그룹 공리는 G의 각 요소가 되돌릴 수 없다는 것이다.이것을 잠시 믿으면서, a가 1 a a p - 1의 범위에 있다고 가정하자, 즉 a는 G의 요소다. k는 a의 순서가 되도록 하자, 즉 k는 1^k mod (mod p)와 같은 가장 작은 양의 정수다.그러면 숫자^{k −1} 1, a, a², a, ...가 G의 서브그룹을 형성하는데 그 순서는 k이고 따라서 라그랑주의 정리로는 k가 g의 순서를 p - 1로 나눈다.그래서 p - 1은 일부 양의 정수 m에 대해 km를 나눈다.

${\displaystyle a^{p-1}\equiv a^{km}\equiv (a^{k})^{m}\equiv 1{\pmod {p}.}$

G의 모든 원소 b를 되돌릴 수 없다는 것을 증명하기 위해, 우리는 다음과 같이 진행할 수 있다.첫째, b는 p와 같은 시간이다.따라서 Bézout의 정체성은 우리에게 bx + py = 1과 같은 정수 x와 y가 있다는 것을 보장한다. 이 동등 모듈로 p를 읽으면 bx ≡ 1 (mod p) 이후 x는 b의 역수임을 알 수 있다.따라서 G의 모든 요소는 되돌릴 수 없다.그래서 앞서 언급했듯이 G는 집단이다.

예를 들어 p = 11일 때 각 원소의 invers는 다음과 같이 주어진다.

a	1	2	3	4	5	6	7	8	9	10
a−1	1	6	4	3	9	2	8	7	5	10

오일러의 증거

이전의 증거를 가져다가 라그랑주의 정리를 이용하는 대신, 이 구체적인 상황에서 증명하려고 하면, 오일러의 세 번째 증거를 얻게 되는데, 그것은 오일러가 더 자연스럽다는 것을 알게 된 것이다.^[10][11]A를 숫자 1, a, a², a, ..., 축소된^{k − 1} 모듈로 p로 설정한다.A = G이면 k = p - 1이고 따라서 k는 p -1을 나눈다.그렇지 않으면 B₁ ∈ G\A가 있다.

A를₁ 숫자 b₁, ab₁, ab²₁, ab, ab, ab^{k − 1}₁ 축소 modulo p로 설정한다.그 다음에 A는₁ k 구별되는 요소를 가지는데, 그렇지 않으면 ab^m₁ ab abⁿ₁ (mod p)과 같이 두 개의 구별되는 숫자 m, 즉 n ∈ {0, 1, ..., k - 1이 있을 것이기 때문에, ≡ aⁿ (mod p)를^m 따를 수 없기 때문이다.반면에, A의₁ 어떤 요소도 A의 요소가 될 수 없다. 그렇지 않으면 ab^m₁ ≡ aⁿ (mod p)와 b₁ ≡ a (mod p)와 같은 숫자 m, n ∈ {0, 1, …, k - 1이 있을 것이고₁, b ≡ a^{nk − m} mod a (mod p)는^{n + k − m} b ∉ A부터 불가능하기 때문이다.

그래서 A setA₁ 세트에는 2k 원소가 있다.만약 G와 동일하다고 판명되면, 2k = p -1이 되고, 따라서 k는 p -1을 나눈다.그렇지 않으면, B₂ g G\(AaA₁)가 있고, 우리는 A를₂ 숫자₂ b, ab₂, ab²₂, ab, ..., ab^{k − 1}₂ 축소된 modulo p를 가진 세트로 정의하면서, 처음부터 다시 시작할 수 있다.G는 유한하므로 이 공정이 어느 시점에서 중단되어야 하며 이는 k가 p - 1을 나눈다는 것을 증명한다.

예를 들어 a = 5이고 p = 13이면

• 5² = 25 ≡ 12 (모드 13),
• 5³ = 125 ≡ 8 (모드 13),
• 5⁴ = 625 ≡ 1 (모드 13),

k = 4이고 A = {1, 5, 8, 12}이(가) 있다.분명히 A ≠ G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.b를₁ G\A의 요소가 되게 하라. 예를 들어, b₁ = 2를 취하라.그럼, 그 이후부터.

• 2×1 = 2,
• 2×5 = 10,
• 2×8 = 16≡ 3 (모드 13),
• 2×12 = 24≡ 11(모드 13),

A₁ = {2, 3, 10, 11}이(가) 있다.분명히 A∪A₁ ≠ G. b를₂ G\(A∪A₁)의 요소가 되게 하라. 예를₂ 들어 b = 4를 취하라.그럼, 그 이후부터.

• 4×1 = 4,
• 4×5 = 20≡ 7 (모드 13),
• 4×8 = 32 6 6 (모드 13),
• 4×12 = 48≡ 9 (모드 13),

A₂ = {4, 6, 7, 9}이(가) 있다.그리고 지금 G = A∪A₁∪A₂.

집합 A, A₁, 등은 사실상 G에서 A의 코세츠라는 점에 유의한다.

메모들