페르마 정리에서 오일러 정리로

앞선 챕터에서 우리는 다음을 배웠다.

• 합동(congruence)
• Fermat's Little Theorem
• Wilson's Theorem

이제 중요한 확장이 등장한다.

소수에만 적용되던 Fermat 정리를
모든 정수 n으로 확장한 것이 Euler's Theorem이다.

1. Euler의 아이디어

Fermat의 소정리는 다음과 같았다.

a^(p−1) ≡ 1 (mod p) (단, gcd(a, p) = 1)

여기서 p는 소수였다.

Euler는 이 조건을 더 일반화했다.

2. Euler의 피 함수 φ(n)

Euler 정리를 이해하려면 먼저 φ(n)이 필요하다.

φ(n)은 다음을 의미한다.

1부터 n까지의 정수 중에서
n과 서로소인 정수의 개수

예시

• φ(6) = 2 → (1, 5)
• φ(8) = 4 → (1, 3, 5, 7)

소인수분해를 이용한 공식

n의 소인수분해가

n = p₁^k₁ · p₂^k₂ · ... · pₙ^kₙ

이라면,

φ(n) = n(1 - 1/p₁)(1 - 1/p₂)...(1 - 1/pₙ)

3. Euler's Theorem

이제 핵심 정리이다.

gcd(a, n) = 1이면

a^φ(n) ≡ 1 (mod n)

예시

n = 30, a = 11

φ(30) = 8

따라서,

11^8 ≡ 1 (mod 30)

4. 핵심 Lemma (증명의 핵심 아이디어)

n과 서로소인 수들을 다음과 같이 두자.

a₁, a₂, ..., a_{φ(n)}

이때 다음 집합을 생각한다.

aa₁, aa₂, ..., aa_{φ(n)}

이 집합은 modulo n에서

a₁, a₂, ..., a_{φ(n)}

과 같은 원소들을 단지 순서만 바꾼 것이다.

5. Euler 정리 증명 아이디어

위 lemma를 이용하면 다음이 성립한다.

a₁ · a₂ · ... · a_{φ(n)}
≡ (aa₁)(aa₂)...(aa_{φ(n)}) (mod n)

우변을 정리하면

≡ a^{φ(n)} · (a₁ · a₂ · ... · a_{φ(n)}) (mod n)

양변에서 공통항을 약분하면

a^{φ(n)} ≡ 1 (mod n)

이 된다.

6. φ(n)의 성질

φ 함수는 다음과 같은 중요한 성질을 가진다.

(1) 소수에 대해

p가 소수이면

φ(p) = p - 1

→ Fermat 정리와 연결됨

(2) 서로소일 때 곱셈성

gcd(m, n) = 1이면

φ(mn) = φ(m)φ(n)

(3) 거듭제곱 형태

φ(p^k) = p^k - p^{k-1}

7. 전체 흐름 연결

지금까지의 정수론 흐름:
Divisibility
↓
GCD (Euclidean Algorithm)
↓
Prime Factorization
↓
Congruence
↓
Fermat's Theorem
↓
Euler's Theorem

Euler 정리는 이 흐름의 자연스러운 확장이다.

8. 왜 중요한가?

Euler 정리는 단순한 정리가 아니다.

다음과 같은 분야의 핵심이다.

• RSA 암호
• 모듈러 연산 최적화
• 역원 계산
• 수론 기반 알고리즘

특히 RSA는 사실상 다음 식 위에 서 있다.

a^φ(n) ≡ 1 (mod n)

핵심 요약

• φ(n)은 n과 서로소인 수의 개수
• Euler 정리: a^φ(n) ≡ 1 (mod n)
• Fermat 정리는 Euler 정리의 특수한 경우
• 증명의 핵심은 집합의 재배열 (permutation)
• φ(n)은 곱셈성을 가진다

이제 정수론은 단순 계산을 넘어
구조 + 함수 + 군 이론으로 확장된다.

Derandomization: Randomness를 제거할 수 있는가?

이전 글에서는 다음 내용을 다루었다.

• Average-case complexity
• Hardness amplification
• Error-correcting codes

이번 글에서는
Randomness를 사용하는 알고리즘을 제거할 수 있는가?라는
핵심 질문을 다룬다.

1. Randomized Algorithms

랜덤 알고리즘은 내부적으로 난수를 사용한다.

예:

$ A(x, r) $

• $x$: 입력
• $r$: 랜덤 비트

기대 실행 시간

$ \mathbb{E}[T(x, r)] $

2. BPP 클래스

정의

$ BPP = { L : \Pr[A(x)=L(x)] \geq \frac{2}{3} } $

즉

• 높은 확률로 정답을 맞추는 알고리즘

특징

• 오류 허용
• 다항시간

3. 핵심 질문

랜덤이 정말 필요한가?

Derandomization 문제

$ BPP \stackrel{?}{=} P $

즉

랜덤 없이도 동일한 계산 가능?

4. 기본 아이디어

랜덤 대신

"좋은 난수처럼 보이는 값" 사용

5. Pseudorandom Generator (PRG)

정의

$ G : {0,1}^s \rightarrow {0,1}^n $

• 짧은 seed → 긴 랜덤처럼 보이는 문자열

조건

어떤 알고리즘도 구분 불가능:

$ | \Pr[A(G(s))=1] - \Pr[A(r)=1] | < \epsilon $

6. Derandomization 구조

랜덤 알고리즘:

$ A(x, r) $

↓

PRG 적용:

$ A(x, G(s)) $

↓

모든 $s$에 대해 실행

결과

랜덤 제거 가능

7. Hardness vs Randomness

핵심 이론:

어려운 함수가 있으면 랜덤을 제거할 수 있다

구조

1. hard function $f$
2. PRG 생성
3. randomness 제거

결과

$ BPP \subseteq P $

(조건부 결과)

8. Nisan-Wigderson Generator

대표적인 PRG 구성

아이디어

• hard function 사용
• overlapping subset 구조

결과

효율적인 PRG 생성

9. Impagliazzo-Wigderson Theorem

중요한 정리

정리

충분히 어려운 함수가 존재하면

$ BPP = P $

의미

• randomness는 본질적이지 않을 수도 있음

10. 복잡도 이론에서 의미

Derandomization은 다음과 연결됨:

• Circuit lower bounds
• Hardness amplification
• Cryptography

11. 핵심 정리

1. Randomized computation

$ A(x, r) $

2. PRG

$ G(s) $

3. Derandomization

$ BPP \rightarrow P $

4. 핵심 아이디어

Hardness → Randomness 제거

결론

Derandomization은 다음 질문에 대한 답이다.

랜덤은 계산에 필수적인가?

현재까지의 결론:

• 이론적으로 제거 가능성 존재
• 하지만 완전한 해결은 아직 미완성

Average-Case Complexity & Hardness Amplification

이전 글에서는 다음 내용을 다루었다.

• $P, NP$
• Circuit Complexity
• $#P$, PP, Toda’s Theorem

이번 글에서는 그 흐름을 이어
Worst-case → Average-case 복잡도 전환을 다룬다.

1. Worst-case vs Average-case

Worst-case complexity

$ T(n) = \max_{x \in {0,1}^n} T(x) $

→ 가장 어려운 입력 기준

Average-case complexity

$ \mathbb{E}_{x \sim D}[T(x)] $

→ 입력 분포 $D$에서 평균 성능

핵심 차이

• Worst-case: 이론 중심
• Average-case: 현실 문제와 밀접

2. Average-case Hardness

문제는 다음 질문이다.

어떤 문제가 평균적으로도 어려운가?

정의 (평균 난이도)

함수 $f$가 평균적으로 어렵다는 것은

$ \Pr_{x \sim D}[A(x) = f(x)] \leq \frac{1}{2} + \epsilon $

즉

• 어떤 알고리즘도 높은 확률로 못 맞춤

3. Hardness Amplification

목표

약하게 어려운 문제 → 매우 어려운 문제로 강화

아이디어

함수 $f$가 약하게 어려울 때

새로운 함수 $g$를 만들어

$ g(x_1, ..., x_k) = f(x_1) \oplus f(x_2) \oplus ... \oplus f(x_k) $

결과

성공 확률 감소:

$ \left(\frac{1}{2} + \epsilon \right)^k $

→ 빠르게 $1/2$로 수렴

4. XOR Lemma

Hardness amplification의 핵심 정리

XOR Lemma

$ f $가 약하게 어렵다면
$ f^{\oplus k} $는 매우 어렵다.

의미

• 여러 번 결합하면
• 예측이 거의 불가능해짐

5. Error-Correcting Codes 연결

Hardness amplification은
Error-Correcting Code와 깊은 연결이 있다.

코드 변환

$ f(x) \rightarrow C(f)(x) $

여기서 $C$는 코드

특징

• 일부 오류 허용
• 전체 정보 복원 가능

복잡도 연결

• 작은 정확도 → 복구 가능
• 계산 어려움 유지

6. Worst-case → Average-case Reduction

핵심 목표:

최악의 경우 어려움 → 평균적으로도 어려움

구조

1. worst-case 문제 $f$
2. 변환 $g$
3. $g$는 average-case hard

결과

암호학에서 매우 중요

7. 암호학과의 연결

Average-case hardness는
암호학의 기반이다.

이유

암호는 다음을 요구한다:

• 대부분 입력에서 어려워야 함

예시

• One-way function
• Pseudorandom generator

8. 핵심 정리

1. Worst vs Average

$ \max $ vs $ \mathbb{E} $

2. Hardness amplification

$ f \rightarrow f^{\oplus k} $

3. XOR Lemma

난이도 강화 핵심 도구

4. Error-Correcting Code

복잡도 + 복원 능력 결합

정리

이번 글의 핵심:

1️⃣ 평균 난이도는 현실 문제의 핵심이다

2️⃣ Hardness amplification은 난이도를 강화한다

3️⃣ XOR Lemma는 핵심 이론이다

Counting Complexity (#P 복잡도)

이전 글에서는 P, NP, NP-Complete와 같은 결정 문제(decision problem) 중심의 복잡도 이론을 살펴보았다.
하지만 실제 계산 문제에서는 단순히 해가 존재하는지 여부보다 더 중요한 질문이 있다.

"해가 몇 개 존재하는가?"

이 질문을 다루는 복잡도 이론이 바로 Counting Complexity이며, 핵심 클래스는 #P이다.

1. Counting Problem

일반적인 결정 문제는 다음과 같은 형태이다.

예:

• 주어진 그래프에 Hamiltonian cycle이 존재하는가?
• Boolean formula가 만족 가능한가?

즉 결과는 Yes / No이다.

하지만 Counting Problem에서는 다음과 같은 질문을 한다.

예:

• Hamiltonian cycle이 몇 개 존재하는가?
• Boolean formula를 만족하는 assignment는 몇 개인가?

이때 우리는 다음과 같은 함수를 정의한다.

$ f(x) = \text{number of solutions of instance } x $

즉 입력 $x$에 대해 가능한 해의 개수를 반환한다.

2. #P Complexity Class

#P (Sharp-P) 는 다음과 같이 정의된다.

NP 문제에서의 증명(witness) 의 개수를 세는 함수의 클래스

정확한 정의는 다음과 같다.

어떤 다항시간 관계 $R(x,y)$ 가 존재하여

$ f(x) = |{y : R(x,y)=1}| $

이면 함수 $f$는 #P에 속한다.

여기서 의미는 다음과 같다.

• $x$ : 문제 인스턴스
• $y$ : witness
• $R(x,y)$ : 다항시간에 검증 가능한 관계

즉

NP는 witness의 존재 여부를 묻고
#P는 witness의 개수를 센다.

3. Example: #SAT

대표적인 #P 문제는 #SAT이다.

SAT 문제는 다음과 같다.

Boolean formula가 만족 가능한가?

반면 #SAT는 다음을 계산한다.

Boolean formula를 만족하는 assignment의 개수

즉

$ f(\phi) = |{x \in {0,1}^n : \phi(x)=1}| $

여기서

• $n$ : 변수 개수
• $\phi(x)$ : Boolean formula

이다.

SAT는 NP-complete이지만
#SAT는 #P-complete 문제이다.

4. Function Complexity Class (FP)

Counting 문제는 결정 문제가 아니라 함수 문제이므로
다음과 같은 클래스가 등장한다.

FP

FP는 다음과 같이 정의된다.

다항시간에 계산 가능한 함수들의 클래스

즉

$ f : {0,1}^* \rightarrow \mathbb{N} $

이면서

$ f(x) $를 다항시간에 계산 가능하면

$ f \in FP $

이다.

5. FP vs #P

두 클래스의 차이는 다음과 같다.

일반적으로 다음 관계가 있다고 믿어진다.

$ FP \neq #P $

즉 대부분의 counting 문제는
다항시간에 계산할 수 없다고 생각된다.

6. Counting vs Decision

Decision 문제와 Counting 문제의 차이를 정리하면 다음과 같다.

예:

SAT 문제

Decision version:

$ \exists x \ \phi(x)=1 $

Counting version:

$ |{x : \phi(x)=1}| $

Counting 문제는 보통 결정 문제보다 더 어렵다.

7. #P-Complete

#P에서도 완전 문제(#P-complete) 개념이 존재한다.

정의:

어떤 문제 $f$가

1. $f \in #P$
2. 모든 $g \in #P$가 $f$로 reduction 가능

이면

$f$는 #P-complete

이다.

대표적인 예는 다음과 같다.

• #SAT
• counting perfect matchings
• counting Hamiltonian cycles

8. 왜 Counting Complexity가 중요한가

Counting 문제는 다양한 분야에서 등장한다.

1. 확률 계산

확률 계산은 종종 다음과 같은 형태이다.

$ P = \frac{\text{good outcomes}}{\text{all outcomes}} $

즉 경우의 수 계산이 필요하다.

2. 통계 물리

물리학에서는 partition function 계산이 중요하다.

$ Z = \sum e^{-E_i / kT} $

이 계산은 많은 경우 #P-hard 문제와 연결된다.

3. 네트워크 분석

그래프에서

• path 개수
• matching 개수
• subgraph 개수

등을 계산해야 한다.

4. 암호학

암호학에서도

• lattice point counting
• solution space size

같은 counting 문제가 등장한다.

9. 핵심 정리

Counting Complexity의 핵심은 다음이다.

1️⃣ NP는 해가 존재하는지 묻는다.

$ \exists y : R(x,y)=1 $

2️⃣ #P는 해의 개수를 센다.

$ f(x)=|{y : R(x,y)=1}| $

3️⃣ 대부분의 counting 문제는 매우 어렵다.

특히

$ #SAT $

같은 문제는 #P-complete이다.

정리

Counting complexity는 복잡도 이론에서 매우 중요한 영역이다.

• NP → 존재 여부
• #P → 해의 개수

많은 실제 문제에서는 결정 문제보다 counting 문제가 더 자연스럽게 등장한다.

따라서

#P 복잡도는 알고리즘 이론, 암호학, 물리학, 네트워크 분석 등 다양한 분야에서 중요한 역할을 한다.

Circuit Lower Bounds와 Proof Complexity 정리

계산 복잡도 이론(Computational Complexity Theory)에서 가장 어려운 문제 중 하나는 어떤 계산이 얼마나 작은 회로로 구현될 수 있는가를 분석하는 것이다.

특히 Circuit Lower Bounds와 Proof Complexity는 복잡도 이론의 핵심 연구 분야이며, 궁극적으로 다음과 같은 근본적인 문제와 연결된다.

• $P \stackrel{?}{=} NP$
• $NP \stackrel{?}{=} coNP$

이번 글에서는 다음 두 가지 주제를 중심으로 정리한다.

1. Circuit Lower Bounds
2. Proof Complexity

1. Circuit Complexity란 무엇인가

Boolean Circuit은 입력 비트를 받아 논리 연산을 수행하는 계산 모델이다.

회로는 보통 다음과 같은 gate들로 구성된다.

• AND
• OR
• NOT

입력 크기를 $n$이라 할 때, 어떤 Boolean 함수 $f$를 계산하는 데 필요한 최소 gate 수를 Circuit Size라고 한다.

이를 수식으로 표현하면 다음과 같다.

$$
size(f)
$$

복잡도 이론에서는 다음과 같은 질문을 한다.

어떤 함수는 최소 얼마 크기의 회로가 필요할까?

만약 어떤 문제에 대해 다음을 증명할 수 있다면

$$
NP \not\subseteq P/poly
$$

즉 NP 문제는 polynomial size circuit으로 계산할 수 없다는 의미이며, 이는 곧

$$
P \neq NP
$$

를 의미하게 된다.

하지만 현재까지 일반적인 circuit lower bound는 거의 알려져 있지 않다.

이 때문에 이 분야는 종종

Complexity theory의 Waterloo

라고 불린다.

2. AC⁰와 Switching Lemma

Circuit complexity 연구에서 가장 중요한 결과 중 하나는 AC⁰ circuit에 대한 lower bound이다.

AC⁰는 다음과 같은 특징을 가진 회로이다.

• constant depth
• AND, OR, NOT gate 사용
• fan-in 제한 없음

즉 매우 얕은 회로 구조이다.

Parity 함수

대표적인 Boolean 함수 중 하나는 Parity 함수이다.

Parity 함수는 다음을 계산한다.

$$
Parity(x_1, x_2, ..., x_n) =
\begin{cases}
1 & \text{if the number of 1s is odd} \
0 & \text{otherwise}
\end{cases}
$$

놀랍게도 이 함수는 AC⁰ 회로로 효율적으로 계산할 수 없다.

즉 다음과 같은 lower bound가 존재한다.

$$
AC^0 \text{ circuit size} \geq \exp(n^{c})
$$

이 결과는 Switching Lemma를 이용하여 증명된다.

Switching Lemma의 아이디어

Switching Lemma는 다음과 같은 아이디어를 사용한다.

입력 변수 일부를 랜덤하게 고정(random restriction)하면 복잡한 Boolean 식이 단순한 형태로 바뀌게 된다.

이를 반복적으로 적용하면

• AC⁰ 회로는 매우 단순한 구조로 변한다.
• Parity 함수는 여전히 복잡한 구조를 유지한다.

따라서

$$
Parity \notin AC^0
$$

임을 증명할 수 있다.

3. ACC Circuit

AC⁰보다 조금 더 강력한 모델이 ACC이다.

ACC 회로는 다음 gate를 사용할 수 있다.

• AND
• OR
• NOT
• MOD gate

MOD gate는 입력 비트 합의 나머지를 계산한다.

예를 들어

$$
MOD_k(x_1, ..., x_n) = (\sum x_i) \bmod k
$$

특히

$$
MOD_2
$$

는 Parity 계산과 동일하다.

ACC는 AC⁰보다 훨씬 강력한 모델이지만 여전히 많은 lower bound 문제가 해결되지 않았다.

최근 중요한 결과 중 하나는 다음과 같다.

$$
NEXP \not\subseteq ACC
$$

이는 일부 매우 어려운 문제들은 ACC 회로로 계산할 수 없다는 의미이다.

4. Monotone Circuit Lower Bounds

Monotone Circuit은 다음과 같은 제약을 가진 회로이다.

• NOT gate 사용 불가능

즉 입력이 증가하면 출력도 증가해야 한다.

이 모델에서는 강력한 lower bound 결과가 알려져 있다.

대표적인 예는 Clique 문제이다.

Clique 문제는 그래프에서 완전 연결된 정점 집합을 찾는 문제이다.

이 문제에 대해 다음 결과가 증명되었다.

$$
\text{Monotone circuit size for Clique} \geq 2^{\Omega(n)}
$$

즉 monotone circuit으로는 clique 문제를 효율적으로 계산할 수 없다.

하지만 일반 circuit에서는 더 작은 회로가 가능할 수도 있다.

이 결과는 monotone circuit과 일반 circuit의 차이를 보여주는 중요한 사례이다.

5. Circuit Complexity의 현재 상황

현재 circuit complexity 연구는 다음과 같은 상태이다.

우리가 알고 있는 것

• AC⁰ lower bound
• monotone circuit lower bound
• 일부 restricted circuit 결과

하지만 여전히 해결되지 않은 문제는 다음과 같다.

$$
P \stackrel{?}{=} NP
$$

또는

$$
NP \stackrel{?}{\subseteq} P/poly
$$

즉 일반적인 circuit lower bound는 아직 거의 증명되지 않았다.

6. Communication Complexity 접근

Circuit lower bound 연구에서는 Communication Complexity라는 도구도 사용된다.

여기서는 다음 상황을 생각한다.

Alice는 $x$를 가지고 있고 Bob은 $y$를 가진다.

그리고 두 사람은 다음 함수를 계산하려고 한다.

$$
f(x,y)
$$

이때 질문은 다음과 같다.

최소 얼마나 많은 정보를 교환해야 할까?

이 문제는 circuit complexity와 연결된다.

특히 다음 관계가 알려져 있다.

$$
\text{Circuit Depth} \leftrightarrow \text{Communication Complexity}
$$

이 관계는 Karchmer–Wigderson game을 통해 연구된다.

7. Proof Complexity

Proof Complexity는 다음 질문을 다루는 분야이다.

어떤 명제를 증명하려면 얼마나 긴 증명이 필요한가

즉 증명의 길이를 계산 복잡도 관점에서 연구한다.

8. Resolution Proof System

가장 유명한 propositional proof system 중 하나는 Resolution이다.

Resolution rule은 다음과 같다.

두 clause가 있을 때

$$
(A \lor B)
$$

$$
(\neg A \lor C)
$$

이 두 식에서 다음을 유도할 수 있다.

$$
(B \lor C)
$$

이 규칙을 반복적으로 적용하면 결국

$$
\Box
$$

(empty clause)을 얻을 수 있다.

이는 해당 formula가 unsatisfiable이라는 의미이다.

9. Proof Size Lower Bounds

Proof complexity에서 중요한 문제는 다음이다.

어떤 명제는 매우 긴 증명이 필요하다.

예를 들어 일부 formula에 대해 다음이 증명되었다.

$$
\text{Resolution proof size} \geq 2^{\Omega(n)}
$$

즉 지수 길이의 증명이 필요하다.

이 결과는 SAT solver의 성능 한계를 이해하는 데도 중요하다.

10. Proof Complexity와 Complexity Theory

Proof complexity 연구는 결국 다음 문제와 연결된다.

$$
NP \stackrel{?}{=} coNP
$$

그 이유는 다음과 같다.

Tautology problem은 다음 클래스에 속한다.

$$
TAUT \in coNP
$$

만약 모든 tautology가 polynomial size proof를 가진다면

$$
NP = coNP
$$

가 된다.

따라서 proof complexity는 복잡도 이론의 핵심 문제와 직접 연결된다.

정리

Circuit lower bounds와 proof complexity는 다음 질문을 연구한다.

Circuit Complexity

어떤 계산은 작은 회로로 불가능한가?

Proof Complexity

어떤 명제는 짧은 증명이 불가능한가?

이 두 분야는 다음과 같은 근본적인 문제를 이해하기 위한 핵심 연구 분야이다.

• $P$ vs $NP$
• $NP$ vs $coNP$

하지만 현재까지 일반적인 circuit lower bound는 거의 알려져 있지 않으며, 이 때문에 이 분야는 여전히 복잡도 이론에서 가장 어려운 연구 영역으로 남아 있다.

Chapter 5. Fermat's Theorem

— 소수와 모듈러 연산의 강력한 성질

앞 장에서는 합동(congruence) 이론을 통해 정수를 나머지 관점에서 바라보았다.

핵심 내용은 다음이었다.

• $a \equiv b \pmod{n}$
• 모듈러 연산
• 선형 합동식
• 중국인의 나머지 정리

이번 장에서는 소수와 모듈러 연산이 만날 때 나타나는 특별한 성질을 배운다.

특히 다음 두 가지 정리가 핵심이다.

• Fermat's Little Theorem
• Wilson's Theorem

이 정리들은 소수의 구조를 이해하는 매우 중요한 도구이며,
현대 암호학에서도 중요한 역할을 한다.

1. Pierre de Fermat

피에르 드 페르마(Pierre de Fermat)는 17세기 프랑스의 수학자이다.

그는 정수론 분야에서 매우 중요한 결과들을 남겼다.

대표적인 업적:

• Fermat's Little Theorem
• Fermat's Last Theorem
• 소수 연구

특히 Fermat's Little Theorem은
모듈러 산술에서 가장 기본적인 성질 중 하나이다.

2. 모듈러 연산과 곱셈 역원

소수 $p$에 대해 모듈러 연산을 생각해보자.

집합

$$
\mathbb{Z}_p = {0,1,2,\dots,p-1}
$$

에서 중요한 특징이 있다.

0을 제외한 모든 원소는 곱셈 역원을 가진다.

즉,

각 $a \neq 0$에 대해 어떤 $b$가 존재하여

$$
ab \equiv 1 \pmod{p}
$$

가 성립한다.

예를 들어 modulo 11에서:

• $3^{-1} \equiv 4$
• 이유: $3 \cdot 4 = 12 \equiv 1 \pmod{11}$

이러한 역원의 존재는 Bézout 정리에서 나온다.

만약 $gcd(a,p)=1$이라면

$$
ax + py = 1
$$

을 만족하는 정수 $x,y$가 존재한다.

따라서

$$
ax \equiv 1 \pmod{p}
$$

이고, $x$는 $a$의 곱셈 역원이 된다.

3. Fermat's Little Theorem

소수 $p$와 정수 $a$에 대해

$$
p \nmid a
$$

라면 다음이 성립한다.

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

이 정리를 Fermat's Little Theorem이라 한다.

예시

$p = 7$, $a = 3$

$$
3^6 = 729
$$

$$
729 \equiv 1 \pmod{7}
$$

실제로 성립한다.

4. Fermat 정리의 아이디어

집합

$$
{1,2,3,\dots,p-1}
$$

을 생각해보자.

이 집합의 모든 원소에 $a$를 곱해보면

$$
a,2a,3a,\dots,(p-1)a
$$

가 된다.

이들을 modulo $p$로 보면
서로 다른 원소가 된다.

따라서 두 집합은 같은 원소들의 재배열이다.

즉,

$$
1 \cdot 2 \cdot 3 \cdots (p-1)
\equiv
a^{p-1}(1 \cdot 2 \cdot 3 \cdots (p-1))
\pmod{p}
$$

양변을 약분하면

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

이 된다.

5. Fermat Pseudoprime

Fermat 정리의 역은 항상 성립하지 않는다.

즉,

$$
a^{n-1} \equiv 1 \pmod{n}
$$

이라고 해서 반드시 $n$이 소수는 아니다.

대표적인 예:

$$
561 = 3 \cdot 11 \cdot 17
$$

하지만

$$
2^{560} \equiv 1 \pmod{561}
$$

이러한 수를 Fermat pseudoprime이라 한다.

특히 모든 $a$에 대해 위 성질이 성립하는 수를
Carmichael number라 한다.

6. Wilson's Theorem

또 다른 유명한 소수 판별 정리:

정수 $p>1$에 대해
$p$가 소수일 필요충분조건은

$$
(p-1)! \equiv -1 \pmod{p}
$$

이다.

이를 Wilson's Theorem이라 한다.

예시

$p = 5$

$$
4! = 24
$$

$$
24 \equiv -1 \pmod{5}
$$

따라서 5는 소수이다.

7. Wilson 정리의 아이디어

modulo $p$에서
각 원소는 곱셈 역원을 가진다.

즉,

각 $a$는 어떤 $a^{-1}$과 짝을 이룬다.

예:

$$
a \cdot a^{-1} \equiv 1
$$

이러한 inverse pairing을 하면
대부분의 항이 1로 사라진다.

결국 남는 것은

• $1$
• $p-1$

뿐이다.

그리고

$$
p-1 \equiv -1 \pmod{p}
$$

따라서

$$
(p-1)! \equiv -1 \pmod{p}
$$

이 된다.

8. 추상대수와의 연결

Fermat 정리는 사실 더 일반적인 정리의 특수한 경우이다.

집합

$$
(\mathbb{Z}/p\mathbb{Z})^*
$$

은 곱셈에 대해 유한군(finite group) 이다.

원소 개수는

$$
p-1
$$

이다.

라그랑주 정리(Lagrange theorem) 에 의해

어떤 원소 $a$에 대해

$$
a^{p-1} = 1
$$

이 된다.

즉,

Fermat's Little Theorem은
라그랑주 정리의 특별한 경우이다.

9. 지금까지의 흐름 정리

정수론의 흐름을 보면 다음과 같다.

Divisibility
↓
GCD & Euclidean Algorithm
↓
Prime Factorization
↓
Congruence
↓
Fermat's Theorem

각 단계는 서로 연결되어 있다.

• gcd → 역원 존재
• 역원 → 모듈러 구조
• 모듈러 구조 → Fermat 정리

핵심 요약

• 소수 $p$에 대해 모든 $a \neq 0$는 곱셈 역원을 가진다.
• Fermat's Little Theorem
  $a^{p-1} \equiv 1 \pmod{p}$
• Fermat pseudoprime과 Carmichael number가 존재한다.
• Wilson's Theorem
  $(p-1)! \equiv -1 \pmod{p}$
• Fermat 정리는 라그랑주 정리의 특수한 경우이다.

이 정리들은 단순한 정수론 결과가 아니라
현대 암호학의 수학적 기반을 형성한다.

앞선 챕터에서 우리는 다음을 배웠다.

- 정수의 나눗셈 구조
- 최대공약수 $gcd(a,b)$
- 소수와 소인수분해
- 소수의 분포

이제 정수론은 한 단계 더 나아간다.

이번 장의 핵심은 다음이다.

> 정수를 "나머지 관점"에서 바라보는 것

이것이 바로 합동(congruence) 이론이다.

1. 합동의 정의

정수 $a, b$와 양의 정수 $n$에 대해

$$
a \equiv b \pmod{n}
$$

이라 함은

$$
n \mid (a - b)
$$

라는 뜻이다.

즉,

> $a$와 $b$를 $n$으로 나누었을 때 나머지가 같다.

예:

- $17 \equiv 5 \pmod{12}$
- 이유: $17 - 5 = 12$

합동은 “같다”는 개념을 나머지 기준으로 확장한 것이다.

2. 합동의 기본 성질

합동은 일반적인 등식처럼 작동한다.

(1) 반사성
$$
a \equiv a \pmod{n}
$$

(2) 대칭성
$$
a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}
$$

(3) 추이성
$$
a \equiv b \pmod{n}, \quad b \equiv c \pmod{n}
\Rightarrow a \equiv c \pmod{n}
$$

따라서 합동은 하나의 동치관계이다.

3. 합동과 연산

합동은 덧셈, 뺄셈, 곱셈과 잘 어울린다.

만약

$$
a \equiv b \pmod{n}
$$

이고

$$
c \equiv d \pmod{n}
$$

라면

- $a + c \equiv b + d \pmod{n}$
- $a - c \equiv b - d \pmod{n}$
- $ac \equiv bd \pmod{n}$

즉, 합동은 연산에 대해 안정적이다.

이 때문에 우리는

$$
\mathbb{Z}_n
$$

이라는 새로운 정수 체계를 만들 수 있다.

4. 나머지 체계와 $\mathbb{Z}_n$

정수를 $n$으로 나누었을 때 가능한 나머지는

$$
0, 1, 2, \dots, n-1
$$

이 집합을

$$
\mathbb{Z}_n
$$

이라 한다.

예:

- $\mathbb{Z}_5 = \{0,1,2,3,4\}$

이 안에서 연산은 항상 나머지 기준으로 계산한다.

예:

$$
4 + 3 \equiv 2 \pmod{5}
$$

왜냐하면 $7 \equiv 2 \pmod{5}$ 이기 때문이다.

이것이 바로 모듈러 산술(Modular Arithmetic)이다.

5. 정수의 이진수와 십진수 표현

정수는 다양한 기수(base)로 표현할 수 있다.

십진법 표현:

$$
a = a_k 10^k + a_{k-1}10^{k-1} + \cdots + a_0
$$

이진법 표현:

$$
a = b_m 2^m + b_{m-1}2^{m-1} + \cdots + b_0
$$

이는 사실 합동과 밀접하다.

왜냐하면:

- 십진수는 $10$을 기준으로 한 표현
- 이진수는 $2$를 기준으로 한 표현

즉, 기수 표현은 합동 이론과 연결되어 있다.

6. 선형 합동식 (Linear Congruence)

가장 기본적인 합동 방정식:

$$
ax \equiv b \pmod{n}
$$

이 방정식이 해를 가지는 조건은

$$
gcd(a,n) \mid b
$$

이다.

이는 Chapter 2에서 배운 유클리드 알고리즘과 직접 연결된다.

즉,

> 합동 방정식은 결국 최대공약수 문제다.

7. 중국인의 나머지 정리 (Chinese Remainder Theorem)

다음과 같은 연립 합동식이 있다고 하자.

$$
x \equiv a_1 \pmod{n_1}
$$
$$
x \equiv a_2 \pmod{n_2}
$$

만약

$$
gcd(n_1, n_2) = 1
$$

이라면,

> 해는 항상 존재하며,  
> $n_1 n_2$를 법으로 유일하다.

이 정리는 매우 강력하다.

왜냐하면:

- 큰 문제를 작은 모듈로 분해할 수 있기 때문이다.
- 현대 암호학(RSA)에서도 사용된다.

8. 이전 챕터와의 연결

지금까지의 흐름을 정리해보자.
Divisibility
↓
GCD & Euclidean Algorithm
↓
Prime Factorization
↓
Prime Distribution
↓
Congruence

합동 이론은 정수론의 구조를 완성한다.

- 나눗셈 → 구조 이해
- 소수 → 기본 구성 요소
- 합동 → 나머지 세계에서의 계산



# 9. 왜 합동이 중요한가?

1. 암호학의 핵심 구조
2. RSA는 모두 모듈러 산술 위에서 작동
3. 해시 함수, 디지털 서명 모두 합동 기반
4. 컴퓨터 내부 연산은 기본적으로 $2$진 합동 체계

합동은 단순한 나머지 계산이 아니다.

> 그것은 정수를 새로운 시각에서 재구성하는 도구다.

핵심 요약

- $a \equiv b \pmod{n}$은 $n \mid (a-b)$를 의미한다.
- 합동은 동치관계다.
- 모듈러 산술은 $\mathbb{Z}_n$ 위에서 작동한다.
- 선형 합동식은 $gcd$와 직접 연결된다.
- 중국인의 나머지 정리는 강력한 구조적 결과다.

이제 정수론은 단순 계산을 넘어서  
구조 이론의 단계로 들어간다.

Chapter 2에서 우리는 정수의 나눗셈 구조를 다뤘다.

- $a \mid b$ (나눗셈의 정의)
- 최대공약수 $gcd(a,b)$
- 유클리드 알고리즘
- Bézout 정리

이제 한 단계 더 나아간다.

> 정수는 무엇으로 구성되어 있는가?

그 답이 바로 소수(Prime)이다.

1. 소수의 정의

정수 $p > 1$이 다음을 만족하면 소수라 한다.

> 약수가 $1$과 $p$뿐인 정수

예:

- $2, 3, 5, 7, 11, 13, 17, \dots$

그 외의 수는 합성수(composite)이다.

2. 정수의 기본정리 (Fundamental Theorem of Arithmetic)

정수론의 핵심 정리:

> 모든 정수 $n > 1$은 소수의 곱으로 유일하게 표현된다.

즉,

$$
n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}
$$

이 표현은 순서를 제외하고 유일하다.

예:

$$
60 = 2^2 \cdot 3 \cdot 5
$$

이 정리는 다음을 의미한다.

- 정수는 소수로 분해된다.
- 그 분해는 단 하나뿐이다.
- 소수는 정수 세계의 기본 구성 요소다.

3. 소수는 무한히 많다

유클리드의 고전적 증명:

소수가 유한하다고 가정하고, 모두 곱한 뒤 1을 더한다.

$$
N = p_1 p_2 \cdots p_k + 1
$$

이 수는 기존 어떤 소수로도 나누어떨어지지 않는다.

따라서 새로운 소수가 존재해야 한다.

→ 모순  
→ 소수는 무한하다.

4. 소수의 개수 함수

소수의 개수를 나타내는 함수:

$$
\pi(x)
$$

이는 $x$ 이하의 소수 개수이다.

예:

- $\pi(10) = 4$
- $\pi(100) = 25$
- $\pi(1000) = 168$

$x$가 커질수록 소수의 밀도는 감소한다.

5. 소수정리 (Prime Number Theorem)

중요한 근사 결과:

$$
\pi(x) \sim \frac{x}{\ln x}
$$

즉, $x$가 충분히 클 때

$$
\pi(x) \approx \frac{x}{\ln x}
$$

이는 다음을 의미한다.

> 큰 수 $x$ 근처에서 정수가 소수일 확률은 약 $1/\ln x$

예:

$10^6$ 근처에서는

$$
\frac{1}{\ln(10^6)} \approx \frac{1}{13.8}
$$

약 14개 중 1개 정도가 소수라는 의미다.

6. Chapter 2와의 연결

Chapter 2에서는 다음을 배웠다.

- 나눗셈 구조
- 최대공약수
- 유클리드 알고리즘
- 선형 결합

Chapter 3에서는 다음을 얻었다.

- 정수는 소수로 유일하게 분해된다.
- 소수는 무한하다.
- 소수는 로그 함수에 따라 점점 희박해진다.

구조적으로 보면:

Divisibility
↓
GCD & Euclidean Algorithm
↓
Prime Factorization
↓
Prime Distribution

7. 왜 중요한가?

1. 소수는 정수의 기본 구성 요소다.
2. 소수의 분포는 수학의 깊은 문제와 연결된다.
3. 큰 소수의 존재는 공개키 암호의 기반이 된다.
4. 소인수분해의 어려움은 보안의 핵심이 된다.

정수론은 단순한 계산 이론이 아니다.

그것은 정수의 구조를 해부하는 이론이며,  
소수는 그 중심에 있다.