#A10 · 대수학 · 수론 (Algebra) · Lv.33D 마인드맵에서 보기

모듈러 합동식과 페르마의 소정리

피에르 드 페르마 · 오일러 · 가우스 · 1640년

a^{p-1} \equiv 1 \pmod{p} \quad (\gcd(a, p) = 1)

a \equiv b \pmod{n} \iff n \mid (a - b)

나머지(Modulo)만을 다루는 시계 산술 체계에서 소수 p에 대해 거듭제곱이 주기적으로 1로 돌아온다는 정수론의 핵심 정리로, 현대 인터넷 보안(RSA 공개키 암호·블록체인)의 심장입니다.

🧮 즉석 공식 계산기 & 그래프 플로터

밑 정수 a

지수 e

소수 모듈러 p

3^{6} \equiv 1 \pmod{7}, \quad 3^{6} \equiv 1 \pmod{7}

3^6 mod 7

1

페르마 a^(p-1) mod p

1

모듈러 역원 a^(p-2)

5

선수 개념 경로 (Prerequisite Path) (5 STEP)

전체 경로 분석기

아래 순서대로 클릭하면 3D 네온 경로를 따라 기초부터 목표 공식까지 정복합니다.

STEP 1#A01등식의 성질과 일차방정식

ax + b = 0 \implies x = -\frac{b}{a}

STEP 2#A02곱셈공식과 인수분해 항등식

(a+b)^2 = a^2 + 2ab + b^2

STEP 3#A03지수법칙과 거듭제곱근

a^m \cdot a^n = a^{m+n}

STEP 4#A08이항정리와 파스칼의 삼각형

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

STEP 5#A10모듈러 합동식과 페르마의 소정리

a^{p-1} \equiv 1 \pmod{p} \quad (\gcd(a

기하학적·직관적 원리 해설

12시간제 시계에서 15시는 3시와 합동(15 ≡ 3 mod 12)입니다. 소수 p로 나눈 나머지 세계에서는 {1, 2, …, p-1} 전체에 a를 곱해도 순서만 뒤섞일 뿐 집합 전체의 곱이 보존되어 a^(p-1) ≡ 1 (mod p)가 성립합니다.

단계별 수식 유도 과정

Step 1.1단계: 소수 p와 서로소인 a에 대해 {a, 2a, 3a, …, (p-1)a} 를 p로 나눈 나머지는 모두 다릅니다.
Step 2.2단계: 따라서 이 나머지들의 집합은 {1, 2, 3, …, p-1} 과 순서만 다른 동일한 집합입니다.
Step 3.3단계: 모든 원소를 곱하면 a^(p-1) · (p-1)! ≡ (p-1)! (mod p) 이고, (p-1)! 을 약분하면 a^(p-1) ≡ 1 (mod p)

AI · 프로그래밍 실전 활용처

HTTPS·금융 보안 RSA 공개키 암호화, 블록체인 전자서명 및 해시 테이블(Hash Map) 충돌 분산

#RSA Cryptography#Blockchain Security#Hash Table Modulo

const modPow = (a: bigint, e: bigint, m: bigint): bigint => /* binary exp */

대수학 · 수론 (Algebra) — 함께 탐험할 연관 공식

등식의 성질과 일차방정식

Lv.1 · Linear Layer y=wx+b

곱셈공식과 인수분해 항등식

Lv.1 · Polynomial Kernel SVM

지수법칙과 거듭제곱근

Lv.1 · IEEE 754 Float

이차방정식 근의 공식과 판별식

Lv.2 · 3D Ray Tracing

근과 계수의 관계 (비에트 정리)

Lv.2 · Matrix Trace & Det

로그의 정의와 밑변환 공식

Lv.2 · O(log N) Complexity