Released · improving
Algorithm
GCD and LCM, modular arithmetic and inverses, fast exponentiation, the sieve of Eratosthenes and nCr mod p: the number theory toolkit for algorithms.
Number theory studies integers, especially division and remainders. In algorithms it means computing GCDs and LCMs with the Euclidean algorithm, working with huge values through modular arithmetic, and finding modular inverses with the extended Euclidean algorithm or Fermat's little theorem. Fast exponentiation, the sieve of Eratosthenes, prime factorization and binomial coefficients modulo a prime complete the toolkit.
These tools show up constantly in coding interviews and contests as "print the answer modulo 10^9 + 7", and in production they underpin public-key cryptography such as RSA and Diffie-Hellman, hash functions, random number generators and check digits. Most of them run in logarithmic or near-linear time, so knowing how they work turns computations that would never finish into ones that take milliseconds.
Start by tracing the rules of modular arithmetic and the Euclidean algorithm by hand, then implement fast exponentiation and the sieve yourself. Move on to modular inverses and nCr mod p, and if you write C++ or Java, practice handling multiplication overflow and negative remainders. Learn the standard helpers too, such as Python's pow(a, e, m) and math.gcd.
Repeating gcd(a, b) = gcd(b, a mod b) finds the GCD in O(log n); the extended version also returns the coefficients of ax + by = gcd(a, b).
Addition, subtraction and multiplication preserve remainders, so you reduce after every step; division becomes multiplication by a modular inverse.
Squaring the base over the binary digits of the exponent computes a^e mod m with about log e multiplications instead of e.
Crossing out multiples of each prime from i × i finds every prime up to n in O(n log log n); a smallest-prime-factor table then factors numbers quickly.
gcd finds the greatest common divisor with the Euclidean algorithm, and the LCM follows as a // gcd(a, b) * b. mod_pow is fast exponentiation: it walks the bits of the exponent, squaring and multiplying, and with a prime modulus p, a^(p-2) gives the modular inverse of a. sieve uses the sieve of Eratosthenes to list every prime up to 30. Save the file and run python number_theory.py.
number_theory.py
import math
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
def mod_pow(base: int, exp: int, mod: int) -> int:
result, base = 1 % mod, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def sieve(n: int) -> list[int]:
is_prime = [False, False] + [True] * (n - 1)
for i in range(2, math.isqrt(n) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i, p in enumerate(is_prime) if p]
MOD = 10**9 + 7
print(gcd(84, 36), 84 // gcd(84, 36) * 36) # 12 252
print(mod_pow(3, 200, 13)) # 9
print(mod_pow(3, MOD - 2, MOD)) # 333333336, the inverse of 3
print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
python number_theory.pySix chapters that take you from installation to the core ideas of Math and number theory.
Ask questions, share experience and trade opinions about Math and number theory.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.