Elementary Number Theory — GCD, LCM, Euler, CRT
GCD/LCM properties, Bézout/Frobenius, Euler’s theorem with power-tower reduction and φ-chain technique, congruence system merging via exGCD, CRT, and n! prime factorisation via Legendre’s formula.
Tags
#Crt
2 posts
Primality, Factorisation & Residues (Miller-Rabin, Pollard Rho, Tonelli-Shanks)
Miller-Rabin primality test, Pollard Rho factorisation, Tonelli-Shanks for quadratic residues, cubic residues via F_p[t]/(t^3-a), quartic residues by double square root, and general k-th residues via primitive root + BSGS, plus …