Number Theory
Reference · Always free
Explore divisibility, primes, modular arithmetic, the Euclidean algorithm, and cryptographic applications.
Concepts in this topic
- Divisibility & Primes - Study divisibility rules, prime numbers, and the Fundamental Theorem of Arithmetic
- Modular Arithmetic - Learn clock arithmetic and congruence relations
- GCD & Euclidean Algorithm - Compute greatest common divisors efficiently
- Applications - Apply number theory to cryptography and other areas
Key formulas & identities
| Name | Formula | Meaning |
|---|---|---|
| Division Algorithm | a = d × q + r, where d > 0 and 0 ≤ r < d | Any integer a divided by positive d gives a unique quotient q and remainder r |
| GCD-LCM Relationship | gcd(a, b) × lcm(a, b) = |a × b| | The product of the GCD and LCM equals the absolute product of the numbers |
| Euclidean Algorithm | gcd(a, b) = gcd(b, a mod b) | The GCD can be computed by repeatedly taking remainders |
| Bézout's Identity | ∃ x, y ∈ ℤ : a × x + b × y = gcd(a, b) | The GCD of two integers can always be expressed as their integer linear combination |
| Fermat's Little Theorem | aᵖ⁻¹ ≡ 1 (mod p) when p is prime and p ∤ a | For prime p, raising a to the (p-1) power gives 1 modulo p |
| Euler's Theorem | aᵠ⁽ⁿ⁾ ≡ 1 (mod n) when gcd(a, n) = 1 | Generalizes Fermat's Little Theorem to any modulus using Euler's totient |
| Euler's Totient (Prime Power) | φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p) | Euler's totient function for a power of a prime |
| Euler's Totient (Product) | φ(a × b) = φ(a) × φ(b) when gcd(a, b) = 1 | Euler's totient is multiplicative for coprime arguments |
Sample practice problem
From the free practice sample - 77 guided problems cover this topic in interactive practice.
Which of the following is a prime number?
- 15
- 21
- 23
- 25
Show answer
Answer: 23
23 is prime (divisible only by 1 and 23). 15 = 3 × 5, 21 = 3 × 7, and 25 = 5 × 5 are all composite.