Number Theory

Euclid’s Proof That Primes Never Run Out #

Any finite list can be used to build a new one.

Any finite list of primes can be used to build a prime it does not contain

Euclid starts by supposing the primes ran out, with every one on a single list.

Multiply every one together and add 1. Nothing on the list divides it.

Each one leaves remainder 1, so this number hides a prime you missed.

Modular Arithmetic on a Clock Face #

Remainders bend the number line into a circle.

Working with remainders turns a number line into a circle

9 o’clock plus 5 hours is 2 o’clock, not 14.

The clock keeps only the remainder after dividing by 12: we write 14 mod 12 = 2.

The number after mod is the modulus. Here it is 5, so the circle holds 0 to 4.

Casting Out Nines to Check Arithmetic #

A digit sum keeps the same remainder.

Adding the digits of a number leaves the same remainder as the number itself does

Each power of ten is a run of nines plus 1, so each leaves remainder 1.

Split 473 into 4·100 + 7·10 + 3. Each power carries 1, so only the digits are left.

473 and its digit sum 14 leave exactly the same remainder, 5.

Now check a sum: 473 + 218 = 691. Do the remainders on both sides agree?

The remainders 5 and 2 add to 7, and 691 leaves 7 too, so the answer checks out.

Why Every Fraction Terminates or Recurs #

Only so many remainders are available.

Every fraction either stops or falls into a repeating cycle, and never does anything else

$\frac{1}{8}$1/8 stops after 3 digits, because 8 is built only from 2s.

Kept as remainders it runs 1, 2, 4, then 0 — and 0 is where the digits stop.

Divide by 7 and 0 never comes. Only six remainders exist, so one must repeat.

10 is 2 × 5, so powers of ten absorb 2s and 5s. Any other factor never clears.

Why 0.999… Equals Exactly One #

Two names for the very same number.

An endless run of nines after the point is exactly the number 1

Each extra nine closes the gap, and no gap is ever left over.

Call it x and multiply by 10. Every nine lines up under a nine.

Subtract: each nine wipes a nine, leaving 9x = 9 — so x = 1.

Turning Recurring Decimals into Fractions #

Shift a block, subtract, done.

Shifting a recurring decimal by its repeat length and subtracting frees the fraction

Multiply until the tails line up, subtract, and the endless part wipes itself out.

One repeating digit needs only × 10: 9x = 5, so $\frac{5}{9}$5/9 — the move that proved 0.999… = 1.

A non-repeating head: shift past it first, then subtract the two shifted copies.

Every repeating decimal falls to this method — that is why each one is rational.

Egyptian Fractions and the Greedy Algorithm #

Any fraction as a sum of distinct unit ones.

Every fraction can be written as a sum of different fractions with one on top

The Egyptians wrote every fraction, like this $\frac{7}{12}$7/12, as unit fractions — all different.

Take the biggest unit fraction that fits, then repeat on what is left.

Being greedy always works here, and the remainder shrinks every time.

The Square Root of Two Is Irrational #

Assume it is a fraction, and it falls apart.

Assuming the square root of two is a fraction leads to a contradiction

Suppose it were a fraction, already canceled down as far as it goes.

Squaring gives $a^2=2b^2$a² = 2b², so $a^2$a² is even, and only even numbers square to even.

Write a = 2k and b comes out even too — so it was never in lowest terms.

Continued Fractions #

The endless fraction that closes in on root two.

A number that no fraction can equal can still be written as a fraction that never ends

$\sqrt{2}$√2 is not equal to any fraction. It is equal to this.

Below the top, every level is the same 2, so the pattern repeats without end.

Stop the tower early and an ordinary fraction falls out. Fold it from the bottom.

Bottom first: $2+\frac{1}{2}$2 + 1/2 is $\frac{5}{2}$5/2, one over that is $\frac{2}{5}$2/5, and $1+\frac{2}{5}=\frac{7}{5}$1 + 2/5 = 7/5.

Every extra level lands nearer, jumping above and below the true value.