Number Theory and Modular Arithmetic TODO
Concept
Modular arithmetic identifies integers by their remainder modulo n; addition, subtraction, and multiplication are all compatible with the remainder operation, but division is only defined when an inverse exists. a has a multiplicative inverse mod n if and only if gcd(a, n) = 1, and that inverse can be obtained via the extended Euclidean algorithm by solving ax + ny = 1. When n is a prime p, every nonzero element has an inverse, making it a finite field; by Fermat's little theorem, a^(p-1) ≡ 1 (mod p), so the inverse can also be computed as a^(p-2). Euler's theorem generalizes this: whenever gcd(a, n) = 1, a^φ(n) ≡ 1 (mod n), which is the basis for how exponents are handled in RSA-type systems. The Chinese Remainder Theorem states that a system of congruences over pairwise coprime moduli has a unique solution modulo their product, and it's used to split large-number arithmetic into computations over smaller moduli.
Elliptic curve operations, hash-to-field, and ZK circuit arithmetic all run over finite fields, so without understanding modular inverses and overflow handling you can't judge either the correctness or the performance of cryptographic code.
Code & Formula
# 정수론·모듈러 산술 — 확장 유클리드로 모듈러 역원 구하기 + 페르마 소정리로 교차검증
# ax + ny = gcd(a, n) 을 풀어 gcd=1이면 x가 곧 a의 (mod n) 역원이다.
def ext_gcd(a, n):
"""확장 유클리드: (g, x, y) with a*x + n*y = g = gcd(a, n)."""
old_r, r = a, n
old_x, x = 1, 0
old_y, y = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return old_r, old_x, old_y
def mod_inverse(a, n):
g, x, _ = ext_gcd(a, n)
if g != 1:
raise ValueError(f"{a}는 mod {n}에서 역원이 없음 (gcd={g})")
return x % n
p = 1_000_000_007 # 큰 소수
for a in (3, 12345, 999_999_999):
inv = mod_inverse(a, p)
check = (a * inv) % p
fermat_inv = pow(a, p - 2, p) # 페르마 소정리: a^(p-2) ≡ a^-1 (mod p)
print(f"a={a:>10} ext_gcd 역원={inv:>10} a*inv mod p={check} "
f"페르마 역원과 일치={inv == fermat_inv}")
# 소수가 아닌 법에서는 gcd(a,n)=1일 때만 역원이 존재함을 확인
n = 20
for a in range(1, n):
from math import gcd
if gcd(a, n) == 1:
print(f"mod {n}: a={a} 역원={mod_inverse(a, n)}")
Exercise
Implement the extended Euclidean algorithm yourself to find the inverse of a modulo an arbitrary prime p, then compute the same value as a^(p-2) mod p and confirm the two results match.
Practical Connection
The reason Solidity fixed-point math uses patterns like mulDiv — multiplying before dividing — and the fact that division over a finite field is really multiplication by an inverse, connect directly to both the precision design of LMSR price calculations and the code that verifies them.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.