1. 개요

• 페르마의 소정리 ( Fermat’s Little Teorem )
  • 어떤 수가 소수일 경우 간단한 필요 조건에 대한 정리이다.

---

2. 정의

2.1 페르마의 소정리 정의

페르마의 소정리 ( Fermat’s little Theorem )
$p$ 가 소수이고 $a$ 가 $p$ 의 배수가 아니면, $a^{p-1}\ \equiv\ 1\ (\ mod\ p\ )$ 이다.

• 위와 같은 식이 왜 성립되는지 증명을 통해 알아보자.

2.2 페르마의 소정리 유도

글을 읽기 이전에 모듈러 연산 에 대한 설명을 읽어보고 오자.

---

2.2.1 식의 정의

• 다음과 같은 크기 $p-1$ 의 집합 $A$가 있다고 하자 ( 이 때, $p$ 는 소수이다. )

• 이 집합 $A$ 의 모든 원소값에 각각 $a$ 를 곱하면 아래와 같다. ( 단, $a$ 는 $p$ 의 배수가 아닌 정수이다. )

• 그럼 이 식을 모듈러 연산을 통해 살펴보면 아래와 같이 보일 것이다.

• 이 과정을 통해 나온 식을 집합 $B$ 라고 하자. 그럼 아래와 같이 보일 수 있다.

위 문단에서 설명한 예시와 같이 $p=5,\ a=2$ 라고 가정하면,

$A=\{\ 1,\ 2,\ 3,\ 4\ \}$ 에 $2$ 를 곱한 집합 $\{\ 2,\ 4,\ 1,\ 3\ \}$ 는 $mod\ 5$ 에서
$\{\ 2,\ 4,\ 1,\ 3\ \}=\{\ 1,\ 2,\ 3,\ 4\ \}$ 가 된다.

• 이를 통해 아래와 같이 정리 가능하다.

---

2.2.1 모듈러 연산을 통한 유도

• 모듈러 연산의 성질을 통해 공식을 유도해보자.

• $A,\ B$ 에 있는 원소들을 각각 곱한뒤 양변에 $mod\ p$ 를 취해준다.

• 위 식을 아래와 같이 풀어서 작성한 다음..

• 이후 양변에 있는 $1\ \times\ 2\ \times\ ...\ \times\ (p-1)$ 을 지우면 아래와 같이 유도가 끝난다.