Number Theory
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Euclidean and extended Euclidean algorithms.
GCD/LCM and Bézout's identity.
Sieve and segmented sieve.
Fermat's little theorem and Euler's theorem.
Euler's totient function.
Chinese Remainder Theorem.
Linear Diophantine equations.
Möbius function and inversion overview.
Miller–Rabin primality test.
Pollard's rho factorization overview.
Fast doubling Fibonacci.
Big integer arithmetic concepts.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Extended Euclid gives Bézout coefficients x, y with ax + by = gcd(a, b), hence modular inverses for any modulus coprime to a (Fermat's a^(p−2) needs a prime modulus).
Linear Diophantine ax + by = c has integer solutions iff gcd(a, b) | c; all solutions are x + k·b/g, y − k·a/g.
Miller–Rabin with the first twelve primes as bases is deterministic for every 64-bit integer; it correctly rejects the Carmichael number 561, which fools the plain Fermat test. Pollard's rho then factors composites in about n^(1/4) expected steps.
Linear sieve marks each composite exactly once (by its smallest prime factor) and computes multiplicative functions such as φ on the way. Möbius inversion: if g(n) = Σ_(d|n) f(d) then f(n) = Σ_(d|n) μ(d) g(n/d).
Fast doubling computes F(n) in O(log n) — the run computes F(10¹⁸) mod 10⁹+7. Big integers store numbers as arrays of base-10⁹ or base-2³² digits with schoolbook or Karatsuba multiplication (Module 20).
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using u64 = unsigned long long; using u128 = __uint128_t;
ll extgcd(ll a, ll b, ll& x, ll& y) { // returns g = gcd(a,b) with a*x + b*y = g (Bezout)
if (b == 0) { x = 1; y = 0; return a; }
ll x1, y1, g = extgcd(b, a % b, x1, y1);
x = y1; y = x1 - (a / b) * y1;
return g;
}
ll modinv(ll a, ll m) { // works for any m with gcd(a, m) = 1
ll x, y; if (extgcd(a, m, x, y) != 1) return -1;
return ((x % m) + m) % m;
}
u64 powmod(u64 b, u64 e, u64 m) { u64 r = 1; b %= m; while (e) { if (e & 1) r = (u128)r * b % m; b = (u128)b * b % m; e >>= 1; } return r; }
bool millerRabin(u64 n) { // deterministic for all 64-bit n with these bases
if (n < 2) return false;
for (u64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) if (n % p == 0) return n == p;
u64 d = n - 1; int s = 0; while (d % 2 == 0) { d /= 2; ++s; }
for (u64 a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
u64 x = powmod(a, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int r = 1
…gcd(240, 46) = 2 = 240*(-9) + 46*(47)
inverse of 3 mod 10 = 7 (3*7 = 21 = 1 mod 10); inverse of 4 mod 10: -1 (none, gcd 2)
6x + 15y = 9: one solution x=-6, y=3
x = 2 mod 3, 3 mod 5, 2 mod 7 -> x = 23 mod 105
Miller-Rabin: 1000000007 prime=true, 561 (Carmichael) prime=false, 2^61-1 prime=true, 999999000001 prime=true
Miller-Rabin agrees with trial division for every n < 100000
phi(1..20): 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8
Euler: 7^phi(20) mod 20 = 1
F(90) = 314255505836800, F(10^18) mod 1e9+7 = 209783453Quiz
? Which method finds a modular inverse when the modulus is not prime?
+ Extended Euclid, when gcd(a, m) = 1 :: The run found 3⁻¹ ≡ 7 mod 10.
- Fermat's a^(m−2) :: Needs a prime modulus.
- Integer division :: Not modular.
- It never exists :: It exists iff gcd = 1.
? Why test 561 with Miller–Rabin rather than Fermat's test alone?
+ 561 is a Carmichael number: a^560 ≡ 1 mod 561 for every a coprime to it, fooling Fermat; Miller–Rabin's square-root check exposes it. :: The run printed prime=false.
- 561 is prime :: It is 3·11·17.
- Fermat's test is slower :: Not the issue.
- Miller–Rabin is only for primes :: It tests any number.
? The CRT system x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7) gave…
+ x = 23 mod 105 :: 23 = 2 mod 3, 3 mod 5, 2 mod 7.
- x = 2 :: 2 is not 3 mod 5.
- No solution :: Coprime moduli always have one.
- x = 53 :: Check: 53 mod 5 = 3, but 53 mod 3 = 2 and 53 mod 7 = 4.