Number Theory & Cryptography

➗ 4.1 Divisibility & Modular Arithmetic

Divisibility Definition

We say a | b (a divides b) if there exists integer k such that b = a·k.

a | b ⟺ ∃k ∈ ℤ : b = a·k Examples: 3 | 12 since 12 = 3·4 ✅ 5 | 30 since 30 = 5·6 ✅ 7 | 15 → 15/7 not integer ❌

🔬 Divisibility Tester

a = b =

Enter values and click Check.

🔬 Find All Divisors

n =

Key Theorems

1

a|b and a|c → a|(b+c) and a|(b−c)

2

a|b → a|(b·c) for any integer c

3

a|b and b|c → a|c (transitivity)

Division Algorithm

For a ∈ ℤ, d ∈ ℤ⁺: a = d·q + r, 0 ≤ r < d q = quotient (a div d) r = remainder (a mod d)

Example: 23 = 5·4 + 3, so 23 div 5 = 4 and 23 mod 5 = 3.

🔬 Division Algorithm

a = d =

Modular Arithmetic

a ≡ b (mod m) means m divides (a−b). Think of a clock — values wrap around after m.

a mod m = r ⟺ a = m·q + r, 0 ≤ r < m Properties: (a + b) mod m = ((a mod m) + (b mod m)) mod m (a · b) mod m = ((a mod m) · (b mod m)) mod m

⏰ Modular Calculator

a = b = mod

⏰ Clock Visualizer

n = mod m =

🔢 4.2 Integer Representations & Algorithms

Base-b Representations

Any positive integer n has a unique representation in base b:

n = aₖ·bᵏ + aₖ₋₁·bᵏ⁻¹ + ... + a₁·b + a₀ Common: Binary(2), Octal(8), Decimal(10), Hex(16)

🔬 Multi-Base Converter

Decimal:

Binary Expansion (Positional Values)

(1101)₂ = 1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 8 + 4 + 0 + 1 = 13

🔬 Binary to Decimal Expander

Binary:

Fast Modular Exponentiation

Compute bⁿ mod m in O(log n) multiplications using repeated squaring — crucial for RSA!

Algorithm: write n in binary, square-and-multiply Example: 3^11 mod 7 11 = (1011)₂ Result built bit-by-bit from MSB

⚡ Modular Exponentiation (Step-by-Step)

b = n = mod =

Binary Addition

🔬 Binary Adder

A: B:

🔑 4.3 Primes & Greatest Common Divisors

Prime Numbers

p > 1 is prime if its only divisors are 1 and p. The Fundamental Theorem of Arithmetic guarantees unique prime factorization for every integer > 1.

Every n > 1 = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ (unique)

🔬 Primality Tester & Factorizer

n =

Sieve of Eratosthenes

Eliminate multiples of each prime starting from 2. What remains are primes.

🧮 Interactive Sieve

Sieve up to:

GCD — Euclidean Algorithm

gcd(a,b) = gcd(b, a mod b) [repeat until b=0] Example: gcd(252,198): 252 = 198·1 + 54 198 = 54·3 + 36 54 = 36·1 + 18 36 = 18·2 + 0 → gcd = 18

🔬 Euclidean Algorithm (Step-by-Step)

a = b =

Extended Euclidean Algorithm (Bézout)

Finds s, t such that: gcd(a,b) = s·a + t·b

🔬 Extended GCD

a = b =

LCM

lcm(a,b) = |a·b| / gcd(a,b)

🔬 LCM Calculator

a = b =

⚖️ 4.4 Solving Congruences

Linear Congruences

ax ≡ b (mod m) Has solution ⟺ gcd(a,m) | b Number of solutions: d = gcd(a,m)

🔬 Linear Congruence Solver: ax ≡ b (mod m)

a = b = m =

Modular Inverse

a⁻¹ mod m exists iff gcd(a,m) = 1. Found via Extended Euclidean.

a · a⁻¹ ≡ 1 (mod m)

🔬 Modular Inverse Finder

a = mod m =

Chinese Remainder Theorem (CRT)

x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) [m₁,m₂ coprime] ... Unique solution mod M = m₁·m₂·...·mₙ

🔬 CRT Solver (2 equations)

x ≡ (mod)

Fermat's Little Theorem

p prime, p ∤ a → a^(p-1) ≡ 1 (mod p) Corollary: a^p ≡ a (mod p)

🔬 Fermat's Little Theorem Verifier

a = p (prime) =

🛠️ 4.5 Applications of Congruences

Hashing

h(k) = k mod m (maps key k to one of m buckets)

🔬 Hash Table Simulator

Buckets m = Keys:

Pseudorandom Numbers — Linear Congruential Generator

x_{n+1} = (a·xₙ + c) mod m Parameters: multiplier a, increment c, modulus m, seed x₀

🎲 LCG Simulator

a = c = m = x₀ = Count =

Check Digits — ISBN-10

Validity: Σᵢ₌₁¹⁰ i·dᵢ ≡ 0 (mod 11) Check digit = (11 - (Σᵢ₌₁⁹ i·dᵢ) mod 11) mod 11

📚 ISBN-10 Check Digit Calculator

First 9 digits:

Calendar — Day of Week

All calendar math reduces to modular arithmetic mod 7.

📅 Day-of-Week Calculator

Year: Month: Day:

🔐 4.6 Cryptography

Caesar / Shift Cipher

Encrypt: C = (P + k) mod 26 Decrypt: P = (C − k + 26) mod 26

🔬 Caesar Cipher

Text: Shift k =

Affine Cipher

Encrypt: C = (a·P + b) mod 26 [need gcd(a,26)=1] Decrypt: P = a⁻¹·(C − b) mod 26

🔬 Affine Cipher

Text: a = b =

RSA Cryptosystem Public Key

1. Pick primes p, q → n = p·q 2. φ(n) = (p−1)(q−1) 3. Choose e: 1 < e < φ(n), gcd(e,φ(n))=1 4. Find d: e·d ≡ 1 (mod φ(n)) Public key: (n, e) Private key: (n, d) Encrypt: C = Mᵉ mod n Decrypt: M = Cᵈ mod n

🔐 RSA Key Generation

p (prime): q (prime): e:

Message M:

Diffie-Hellman Key Exchange Key Agreement

Public: prime p, generator g Alice picks secret a → sends A = gᵃ mod p Bob picks secret b → sends B = gᵇ mod p Shared secret: K = Bᵃ mod p = Aᵇ mod p = g^{ab} mod p (Eavesdropper sees A,B,p,g but cannot find K without discrete log)

🤝 Diffie-Hellman Simulator

p: g: Alice a: Bob b:

Euler's Totient φ(n)

φ(n) = count of integers in [1,n] coprime to n φ(p) = p−1 (p prime) φ(pq) = (p−1)(q−1) (p,q distinct primes)

🔬 Euler Totient Calculator

n =