Number Theory Reference

Discrete Math · Axiom Academy

FORMULA SHEET Number Theory Reference Comprehensive reference for divisibility, modular arithmetic, primes, and cryptography For any integers a and b > 0, there exist unique integers q (quotient) and r (remainder) satisfying the above, where 0 ≤ r < b Repeatedly apply division algorithm until remainder is 0. The last non-zero remainder is gcd(a,b). Finds coefficients x and y (Bézout coefficients) such that gcd(a,b) = ax + by. Essential for solving linear congruences. Read as "a is congruent to b modulo n" Equivalent characterizations of congruence a has a multiplicative inverse modulo n if and only if gcd(a,n) = 1 Find inverse using extended Euclidean algorithm If n₁, n₂, ..., nₖ are pairwise coprime, the system has a unique solution modulo N = n₁n₂...nₖ If p is prime and gcd(a,p) = 1 Equivalent form, holds for all integers a If gcd(a,n) = 1, where φ(n) is Euler's totient function φ(n) counts integers from 1 to n that are coprime to n p is prime if and only if (p-1)! ≡ -1 (mod p) Useful for primality testing (though inefficient for large p) EULER'S TOTIENT FUNCTION PROPERTIES FUNDAMENTAL THEOREM OF ARITHMETIC Every integer n > 1 has a unique prime factorization (up to order of factors) π(x) counts the number of primes ≤ x. Primes become less dense but never run out. Security relies on difficulty of factoring large n = pq. Common values: e = 65537, |p| = |q| ≈ 1024-2048 bits. Solution exists if and only if gcd(a,n) | b If gcd(a,n) = 1, unique solution:

This is the written version of the interactive lesson above. See the full Discrete Math course.