#A10 · 代数学・数論 (Algebra) · Lv.33Dマインドマップで見る

合同式とフェルマーの小定理

Pierre de Fermat, Euler & Gauss · 1640년

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

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

余りだけを扱う時計算術において素数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公開鍵暗号、ブロックチェーン電子署名、ハッシュテーブルのインデックス分散

#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