# Number Theory: The Secret Life of Integers > Number theory is the math of which numbers behave nicely - and it is the reason your credit card number can travel over the internet without being stolen. This guide starts from prime fingerprints and builds up to the clock math that secures your browser. --- # Number Theory: The Secret Life of Integers If you have ever entered a credit card number on a website, sent a private message, or logged into a service that uses HTTPS, you have used number theory. The difference is that the computer knew it was using number theory, and you did not. This guide fixes that. We are not going to prove theorems for the sake of proving theorems. We are going to start from a simple question - "can every number be built from smaller numbers?" - and follow it to the doorstep of modern cryptography. By the end, you will understand why multiplying two large primes is easy, but undoing it is nearly impossible, and why that single fact keeps your data safe. This is the seventh guide in the Mathematics track. It assumes the number families from [Numbers & Number Systems](/guides/numbers-and-number-systems) and the modular arithmetic from Phase 3 of that guide. If you can do long division and understand what a remainder is, you are ready. ## How to read this - **Here for the "how does my browser stay safe" answer?** Start with [Phase 1](01-primes-and-the-building-blocks-of-numbers.md) - primes as unique fingerprints. - **Want the full story?** Read in order - the clock math in Phase 2 sets up the cryptography in Phase 3. ## The phases 1. **[Primes and the Building Blocks of Numbers](01-primes-and-the-building-blocks-of-numbers.md)** - prime factorization as a unique fingerprint, and why some numbers are the atoms of arithmetic. 2. **[The Clock Math You Already Know](02-the-clock-math-you-already-know.md)** - modular arithmetic extended: remainders, modular exponentiation, and why the same trick that tells you what time it is also secures your data. 3. **[How the Internet Stays Secret](03-how-the-internet-stays-secret.md)** - RSA encryption explained as "two large primes multiplied together are easy to compute but nearly impossible to reverse," with the builder's guide to hashing and checksums. > This builds on [Numbers & Number Systems](/guides/numbers-and-number-systems) (integers, primes, modular arithmetic) and pairs with [Counting & Combinatorics](/guides/counting-and-combinatorics) (the pigeonhole principle). It is the discrete math backbone of modern computing. --- # Primes and the Building Blocks of Numbers ## The LEGO brick analogy Think about building with LEGO. Some bricks are basic: the 1x1, the 2x4, the 2x2. Others are fancy: a wheel, a window, a minifigure head. But every model you build, no matter how complex, is a combination of those basic bricks. Numbers work the same way. The basic bricks are **prime numbers** - numbers that cannot be broken down into smaller whole-number pieces. Every other number is a combination of primes, and that combination is unique. That is not a metaphor. It is a theorem, and it is one of the most useful facts in all of mathematics. ## What a prime number is A **prime number** is a whole number greater than 1 that has exactly two divisors: 1 and itself. The first few primes are: ``` 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... ``` Notice that 2 is the only even prime. Every other even number can be divided by 2, so it has at least three divisors: 1, 2, and itself. That disqualifies it. A number that is not prime is **composite**. It can be built from smaller numbers. ``` 4 = 2 * 2 6 = 2 * 3 8 = 2 * 2 * 2 9 = 3 * 3 10 = 2 * 5 ``` ## The fundamental theorem of arithmetic Here is the remarkable part. Take any composite number and break it into primes. You will always get the same primes, no matter how you do it. ``` 12 = 2 * 2 * 3 12 = 3 * 2 * 2 12 = 2 * 3 * 2 ``` The primes are always two 2s and one 3. The order does not matter. The combination is unique. This is called the **fundamental theorem of arithmetic**. It means primes are the unique building blocks of the whole numbers. As every LEGO model can be taken apart into basic bricks, every number can be factored into primes, and there is only one way to do it. That uniqueness is what makes primes useful for cryptography. If a number has only one factorization, then knowing the factors is a very special piece of information. ## Finding the factors: trial division Suppose you want to factor 91. You do not need a computer. You need patience and a simple rule: if a number is composite, it has a factor less than or equal to its square root. The square root of 91 is about 9.5. So you only need to test prime numbers up to 9: 2, 3, 5, 7. - 91 is odd, so not divisible by 2. - 9 + 1 = 10, which is not divisible by 3, so 91 is not divisible by 3. - 91 does not end in 0 or 5, so not divisible by 5. - 91 divided by 7 is 13. Both are prime. So: ``` 91 = 7 * 13 ``` That is the whole factor tree. Two primes, done. ## Greatest common divisor: the largest piece that fits both Suppose you have two numbers, like 48 and 18. You want the largest number that divides both of them evenly. That is the **greatest common divisor**, or GCD. One way to find it: list the factors of each and pick the largest one they share. ``` Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48 Factors of 18: 1, 2, 3, 6, 9, 18 Common: 1, 2, 3, 6 GCD(48, 18) = 6 ``` For small numbers that works. For large numbers, there is a faster method called the Euclidean algorithm. The idea is beautiful in its simplicity: ``` GCD(a, b) = GCD(b, a mod b) ``` Keep taking the remainder until you hit zero. The last non-zero remainder is the GCD. ``` GCD(48, 18): 48 mod 18 = 12 GCD(18, 12): 18 mod 12 = 6 GCD(12, 6): 12 mod 6 = 0 GCD is 6 ``` The same math, faster. And it is the same math that underpins the RSA encryption you will meet in Phase 3. ## See it run Here is a simple factor finder and GCD calculator in Python. ```python runnable def prime_factors(n): factors = [] d = 2 while d * d <= n: while n % d == 0: factors.append(d) n = n // d d = d + 1 if n > 1: factors.append(n) return factors def gcd(a, b): while b: a, b = b, a % b return a print("Factors of 91:", prime_factors(91)) print("Factors of 100:", prime_factors(100)) print("GCD(48, 18):", gcd(48, 18)) print("GCD(1071, 462):", gcd(1071, 462)) ``` *What just happened:* The `prime_factors` function divides the number by successive integers, collecting the prime factors as it goes. The `gcd` function implements the Euclidean algorithm: repeatedly replace the larger number with the remainder until the remainder is zero. Both are fast, both are exact, and both are built on the same prime-number foundation. ## For builders Primes and GCD are not only school topics. They are the tools that make modern security possible. - **Hashing and checksums** - A good hash function spreads inputs evenly across its output range. Prime-number table sizes help avoid the clustering that causes collisions. - **Cryptography** - RSA encryption relies on the fact that multiplying two large primes is fast, but factoring their product back into the original primes is slow. That one-way street is what keeps your data private. - **Periodic scheduling** - If two events repeat on cycles of 3 days and 5 days, they will coincide every 15 days. That is the least common multiple, which is closely related to the GCD. - **Random number generation** - Many pseudo-random number generators use prime moduli to ensure long periods before the sequence repeats. > The key insight: primes are the atoms of arithmetic. Every composite number is a molecule made from prime atoms, and the factorization is unique. That uniqueness is rare in mathematics, and it is the reason primes are useful for everything from hash tables to nation-state encryption. ## What we have built - A **prime** is a number with exactly two divisors: 1 and itself. - A **composite** number can be factored into primes. - The **fundamental theorem of arithmetic** says every number has exactly one prime factorization. - **Trial division** finds factors by testing primes up to the square root. - The **GCD** is the largest number that divides two numbers evenly, found efficiently by the Euclidean algorithm. - In code, prime factorization and GCD are short functions that run on numbers of any size your language can hold. A quick check before you move on: ```quiz [ { "q": "Which of these numbers is prime?", "choices": ["15", "21", "29", "33"], "answer": 2, "explain": "29 has no divisors other than 1 and 29. The others are composite: 15 = 3 * 5, 21 = 3 * 7, 33 = 3 * 11." }, { "q": "What does the fundamental theorem of arithmetic say?", "choices": ["Every number is prime", "Every composite number can be factored into primes in exactly one way", "Prime numbers are infinite", "The GCD of two numbers is always 1"], "answer": 1, "explain": "The fundamental theorem of arithmetic states that every integer greater than 1 can be represented in exactly one way as a product of prime numbers, up to the order of the factors." }, { "q": "Using the Euclidean algorithm, what is GCD(1071, 462)?", "choices": ["21", "33", "7", "3"], "answer": 0, "explain": "1071 mod 462 = 147. 462 mod 147 = 21. 147 mod 21 = 0. The last non-zero remainder is 21, so GCD(1071, 462) = 21." } ] ``` --- # The Clock Math You Already Know ## The clock that never ends In [Numbers & Number Systems](/guides/numbers-and-number-systems) you met modular arithmetic as "clock math." If it is 10 o'clock and you add 5 hours, you do not get 15 o'clock. You get 3 o'clock. The clock wrapped the number around. That instinct is the whole idea. Modular arithmetic is the math of wrap-around. The only difference between a 12-hour clock and the math used in cryptography is the size of the clock face. ## The modulo operation, again If you have two numbers, `a` and `n`, then `a mod n` is the remainder when you divide `a` by `n`. The result always lands between 0 and `n - 1`. ``` 17 mod 5 = 2 because 17 = 3 * 5 + 2 10 mod 12 = 10 because 10 = 0 * 12 + 10 15 mod 12 = 3 because 15 = 1 * 12 + 3 ``` The `n` is the **modulus** - the size of the clock face. When the modulus is 12, you are telling time. When the modulus is a 300-digit prime number, you are doing cryptography. The operation is identical. ## Modular addition and multiplication You can add and multiply inside modular arithmetic, and the wrap-around happens automatically. ``` (7 + 5) mod 12 = 12 mod 12 = 0 (8 * 4) mod 12 = 32 mod 12 = 8 ``` The first line says "7 o'clock plus 5 hours lands on 12, which the clock counts as 0." The second says "8 times 4 is 32, which is 8 past two full cycles of 12." This is useful because it keeps numbers small. In cryptography, you often work with numbers that have hundreds of digits. Modular arithmetic lets you reduce them to a manageable size at every step, without losing the security properties that make the system work. ## Modular exponentiation: repeated multiplication with wrap-around Suppose you want to compute `7^4 mod 12`. That means "multiply 7 by itself 4 times, then wrap the result around a 12-hour clock." ``` 7^4 = 7 * 7 * 7 * 7 = 2401 2401 mod 12 = 1 ``` So `7^4 mod 12 = 1`. For small numbers you can compute the power and then take the remainder. For the huge numbers used in cryptography, that approach is far too slow. The trick is to reduce modulo at every step: ``` 7^2 mod 12 = 49 mod 12 = 1 7^4 mod 12 = (7^2)^2 mod 12 = 1^2 mod 12 = 1 ``` Same answer, but the intermediate numbers never grow larger than the modulus. This is called **modular exponentiation**, and it is the engine behind RSA encryption. ## The Euclidean algorithm, again In Phase 1 you met the Euclidean algorithm for finding the GCD. It works by repeatedly taking remainders: ``` GCD(a, b) = GCD(b, a mod b) ``` That is modular arithmetic in action. The `mod` operation is doing the work. The algorithm stops when the remainder hits zero, and the last non-zero remainder is the GCD. The Euclidean algorithm is fast even for numbers with hundreds of digits. That speed is essential for RSA: the encryption and decryption steps both rely on computing a GCD (or its cousin, the modular inverse) on very large numbers. ## Congruence: same position on the clock You will sometimes see this notation: ``` a ≡ b (mod n) ``` Read it as "a is congruent to b modulo n." It means `a` and `b` leave the same remainder when divided by `n`. They sit at the same position on the clock. ``` 15 ≡ 3 (mod 12) because both leave remainder 3 17 ≡ 2 (mod 5) because both leave remainder 2 ``` Congruence is not the same as equality. `15` is not equal to `3`, but on a 12-hour clock they are indistinguishable. That is all the notation means: different numbers, same position once you wrap. ## See it run Here is modular exponentiation and the Euclidean algorithm in Python. ```python runnable # Modular exponentiation: compute (base ** exp) % mod efficiently def mod_pow(base, exp, mod): result = 1 base = base % mod while exp > 0: if exp % 2 == 1: result = (result * base) % mod exp = exp // 2 base = (base * base) % mod return result # Euclidean algorithm for GCD def gcd(a, b): while b: a, b = b, a % b return a print("7^4 mod 12 =", mod_pow(7, 4, 12)) print("2^10 mod 1000 =", mod_pow(2, 10, 1000)) print("GCD(1071, 462) =", gcd(1071, 462)) ``` *What just happened:* The `mod_pow` function computes `base ** exp % mod` without ever calculating the full power. It squares the base and halves the exponent at each step, reducing modulo at every stage. The `gcd` function is the same Euclidean algorithm from Phase 1, written in a compact loop. Both are the building blocks of the RSA encryption you will meet next. ## For builders Modular arithmetic is not only for clocks and cryptography. It is hiding in tools you use every day. - **Hash tables** - The `hash(key) % num_buckets` operation that decides which bucket a key goes into is modular arithmetic. The hash might be a huge number. The modulus folds it into a valid index. - **Circular buffers** - A ring buffer of size `n` uses `index mod n` to wrap around from the end back to the start. No `if` statement needed. - **Checksums and parity bits** - A parity bit records whether the number of 1-bits is even or odd. That is `count mod 2`. Larger checksums use bigger moduli but the same remainder idea. - **Time and date math** - Days of the week, months of the year, leap years: all modular arithmetic. "What day is it in 100 days?" is `100 mod 7` steps forward from today. > The key insight: modular arithmetic is the math of cycles. Any time something repeats - hours, days, buffer positions, hash buckets - the same operation `a mod n` tells you where you are in the cycle. Cryptography uses very large cycles with very special properties. ## What we have built - **Modular arithmetic** is wrap-around math: `a mod n` is the remainder when `a` is divided by `n`. - **Modular addition and multiplication** keep numbers small by wrapping at every step. - **Modular exponentiation** computes huge powers modulo `n` efficiently, by reducing at every step. - The **Euclidean algorithm** finds the GCD using only the `mod` operation. - **Congruence** `a ≡ b (mod n)` means `a` and `b` share the same remainder. - In code, `%` is the modulo operator, and `mod_pow` is the fast way to compute large powers modulo a number. A quick check before you move on: ```quiz [ { "q": "What is (17 + 9) mod 12?", "choices": ["2", "14", "26", "5"], "answer": 0, "explain": "17 + 9 = 26. 26 mod 12 is the remainder when 26 is divided by 12: 26 = 2 * 12 + 2, so the answer is 2. On a clock, 17 hours past midnight plus 9 hours lands at 2 o'clock." }, { "q": "Why is modular exponentiation important for cryptography?", "choices": ["It makes numbers look bigger", "It lets you compute huge powers modulo a large number without ever calculating the full power, keeping intermediate values small", "It is the only way to compute exponents", "It replaces multiplication with addition"], "answer": 1, "explain": "In RSA, you compute powers of numbers with hundreds of digits. Computing the full power would be impossible. Modular exponentiation reduces modulo at every step, so the intermediate values never exceed the modulus." }, { "q": "What does a ≡ b (mod n) mean?", "choices": ["a equals b", "a and b are both prime", "a and b leave the same remainder when divided by n", "a is larger than b by a multiple of n"], "answer": 2, "explain": "Congruence modulo n means a and b have the same remainder when divided by n. They are in the same position on the n-sized clock, even though the numbers themselves may be very different." } ] ``` --- # How the Internet Stays Secret ## The padlock in your browser Look at the address bar of your browser right now. If you see a little padlock, that means the connection between your computer and the website is encrypted. Your credit card number, your password, your private messages - they are all scrambled into gibberish before they leave your computer, and only the website can unscramble them. The math that makes this possible is number theory. Not the vague "math is beautiful" kind. The specific, practical kind: prime numbers, modular arithmetic, and the fact that some operations are easy to do but very hard to undo. ## The one-way street Here is the core idea, stripped to its essence: **Multiplying two large prime numbers is fast. Factoring their product back into the original primes is slow.** If I give you the number 91 and ask for its factors, you can find 7 and 13 in seconds. But if I give you a 300-digit number that is the product of two 150-digit primes, even the fastest supercomputers on Earth would need longer than the age of the universe to find the original primes. That asymmetry is the foundation of RSA encryption. ## How RSA works, in plain English RSA is a public-key cryptosystem. That means there are two keys: a public key that anyone can see, and a private key that only the website possesses. The public key is built from two large primes, `p` and `q`, and their product `n = p * q`. The private key is derived from `p` and `q`. When you send a message to the website: 1. You look up its public key `(n, e)`. 2. You encrypt your message using `n` and `e`. The encryption is modular exponentiation: `ciphertext = message^e mod n`. 3. The website receives the ciphertext and decrypts it using its private key `d`: `message = ciphertext^d mod n`. The magic is that anyone can compute step 2, but only someone who knows `d` can reverse it in step 3. And `d` is derived from `p` and `q`, which are hidden inside `n`. Without factoring `n`, you cannot find `d`. That is the whole system. The security does not come from keeping the algorithm secret. It comes from the fact that factoring a large composite number is computationally hard. ## A tiny example with real numbers Real RSA uses primes with hundreds of digits. To show the mechanics, we will use tiny primes. Choose `p = 5` and `q = 11`. Then: ``` n = p * q = 55 phi = (p - 1) * (q - 1) = 4 * 10 = 40 ``` Choose `e = 7` (it must be coprime to 40). The public key is `(55, 7)`. To encrypt the message `m = 12`: ``` ciphertext = 12^7 mod 55 ``` Compute step by step: ``` 12^2 mod 55 = 144 mod 55 = 34 12^4 mod 55 = 34^2 mod 55 = 1156 mod 55 = 16 12^7 mod 55 = 12^4 * 12^2 * 12^1 mod 55 = 16 * 34 * 12 mod 55 = 6528 mod 55 = 23 ``` The ciphertext is 23. Without knowing `p` and `q`, an attacker sees only `n = 55` and `ciphertext = 23`. They would need to factor 55 to recover `p` and `q`, compute `phi`, and find the private key `d`. With tiny numbers that is easy. With 300-digit numbers, it is not. ## Hashing: the fingerprint that never lies Encryption is two-way: you encrypt with a public key and decrypt with a private key. Hashing is one-way: you turn data into a fixed-size fingerprint, and you cannot get the original data back from the fingerprint. A **hash function** takes any input - a password, a file, a message - and produces a fixed-length string of bytes. Good hash functions have two properties: 1. **Deterministic** - the same input always produces the same output. 2. **Avalanche effect** - changing even one bit of the input completely changes the output. When you create an account on a website, the site does not store your password in plain text. It stores the hash of your password. When you log in, it hashes the password you typed and compares the hash to the stored hash. If they match, you are in. If the site is breached, the attacker steals the hashes, not the passwords. Because hashing is one-way, the attacker cannot reverse the hashes to get the original passwords. They can only try guessing passwords, hashing each guess, and checking if the hash matches. ## Checksums: catching accidents, not enemies A **checksum** is a small piece of data computed from a larger piece of data. Its job is to detect accidental errors, not to stop deliberate attacks. When you download a file, the website may publish a checksum alongside it. After the download completes, your computer computes the checksum of the downloaded file and compares it to the published value. If they match, the file arrived intact. If not, something went wrong during transmission - a bit got flipped, a packet was lost, a cosmic ray struck the hard drive. Checksums use the same modular arithmetic you have been learning. A simple checksum might add up all the bytes in a file and take the result modulo 256. A more robust one, like CRC32, uses polynomial division over GF(2) - which is modular arithmetic with a different set of rules. The point is the same: reduce a large, error-prone thing to a small, reliable thing, using the wrap-around property of modular arithmetic. ## See it run Here is a tiny RSA encryption and decryption, plus a simple hash function. ```python runnable # Tiny RSA with p=5, q=11 p = 5 q = 11 n = p * q phi = (p - 1) * (q - 1) e = 7 # public exponent # Find d such that (d * e) mod phi = 1 # For this tiny example, d = 23 works because 23 * 7 = 161, and 161 mod 40 = 1 d = 23 def rsa_encrypt(m, e, n): return pow(m, e, n) def rsa_decrypt(c, d, n): return pow(c, d, n) message = 12 ciphertext = rsa_encrypt(message, e, n) decrypted = rsa_decrypt(ciphertext, d, n) print("Original message:", message) print("Ciphertext:", ciphertext) print("Decrypted:", decrypted) # A simple hash function using modular arithmetic def simple_hash(data, mod=256): h = 0 for char in data: h = (h * 31 + ord(char)) % mod return h print("Hash of 'hello':", simple_hash("hello")) print("Hash of 'hello!':", simple_hash("hello!")) ``` *What just happened:* The RSA section encrypted the number 12 with public key `(55, 7)` to get ciphertext 23, then decrypted it with private key `d = 23` to get 12 back. The `pow(base, exp, mod)` function is Python's built-in modular exponentiation - fast even for huge numbers. The `simple_hash` function turns a string into a number between 0 and 255 by iterating over the characters, multiplying the current hash by 31, adding the character code, and taking the result modulo 256. Change one character and the hash changes completely. ## For builders This is the part where number theory stops being abstract and starts being the reason your software is secure. - **HTTPS and TLS** - The padlock in your browser is RSA (or its modern cousin, elliptic curve cryptography) in action. The handshake that sets up the encrypted channel is pure number theory. - **Password storage** - When a site hashes your password instead of storing it in plain text, it is using a one-way function. The best hash functions for passwords, like bcrypt and Argon2, are designed to be slow on purpose, to make guessing expensive. - **Blockchain and cryptocurrencies** - Bitcoin and Ethereum use elliptic curve cryptography, which is number theory with a different curve. The "private key" is a random number. The "public key" is a point on a curve derived from that number. You can share the public key freely; only the private key can sign transactions. - **Version control** - Git uses SHA-1 (and is moving to SHA-256) to identify commits. The hash is a checksum of the commit contents. If even one bit changes, the hash changes, and Git knows something is wrong. - **Load balancing and consistent hashing** - When a distributed cache needs to decide which server holds a key, it hashes the key and takes the result modulo the number of servers. Adding or removing a server only moves the keys that fall into the changed range. > The key insight: number theory gives us one-way functions. Easy to compute in one direction, hard to reverse. That asymmetry is the foundation of all digital security. Without it, the internet as we know it could not exist. ## What we have built - **Prime numbers** are the atoms of arithmetic. Every composite number has a unique prime factorization. - The **fundamental theorem of arithmetic** guarantees that factorization is unique. - The **Euclidean algorithm** finds the GCD efficiently using only the `mod` operation. - **Modular arithmetic** is wrap-around math. It keeps numbers small and enables cycles. - **Modular exponentiation** computes huge powers modulo `n` efficiently, by reducing at every step. - **RSA encryption** works because `n = p * q` is easy to compute, but factoring `n` back into `p` and `q` is hard. - **Hashing** turns data into a fixed-size fingerprint using one-way functions. - **Checksums** detect accidental errors using modular reduction. You started this guide with a simple question about building blocks. You ended at the doorstep of the encryption that protects your credit card number. The same prime numbers that make multiplication unique also make factoring hard, and that hardness is what keeps your data safe. A quick check before you go: ```quiz [ { "q": "Why is RSA encryption secure?", "choices": ["Because the algorithm is kept secret", "Because multiplying two large primes is easy, but factoring their product back into the original primes is computationally hard", "Because the primes are so large that computers cannot store them", "Because the modulus is always a prime number"], "answer": 1, "explain": "RSA security relies on the asymmetry between multiplication and factoring. Given two large primes p and q, computing n = p * q is fast. Given only n, recovering p and q by factoring is infeasible for sufficiently large numbers." }, { "q": "What is the main difference between encryption and hashing?", "choices": ["Encryption is faster than hashing", "Encryption is two-way (you can decrypt), while hashing is one-way (you cannot get the original data back)", "Hashing uses primes and encryption does not", "Encryption is used for passwords and hashing is used for files"], "answer": 1, "explain": "Encryption is designed to be reversed with the right key. Hashing is designed to be one-way: you can compute a hash from data, but you cannot recover the original data from the hash. That is why sites store password hashes instead of plain-text passwords." }, { "q": "A website publishes a checksum alongside a file you are downloading. What is the checksum checking for?", "choices": ["Whether the file contains a virus", "Whether the file was intentionally tampered with by an attacker", "Whether the file arrived intact without accidental corruption", "Whether the file is the latest version"], "answer": 2, "explain": "A checksum detects accidental errors in transmission or storage - a flipped bit, a lost packet, a scratched disk. It is not designed to stop deliberate tampering; for that you need a cryptographic signature or hash." } ] ```