Whenever abstract algebra invents something new (a group, a ring, an ideal), the first example anyone checks it against is $\mathbb{Z}$. So before we build anything, we need to know the integers really well. You've been using everything on this page since grade school: dividing with remainders, finding a greatest common factor, breaking numbers into primes. Now we prove it all, and on the way we pick up the two proof tools that hold the integers together: induction and well-ordering.
Suppose you want to prove something about every natural number at once: a formula, an inequality, a divisibility fact. You can't check infinitely many cases one at a time. Induction trades all of those cases for just two checks.
Principle of Mathematical Induction. Suppose that $\forall n \in \mathbb{N}$, $S(n)$ is a logical statement, and that:
Then $S(n)$ is true for all $n \in \mathbb{N}$.
In practice, that turns into a three-step recipe. To prove that $S(n)$ is true, $\forall n \in \mathbb{N}$:
Conclude that $S(n)$ is true, $\forall n \in \mathbb{N}$.
The inductive step is the part that feels like cheating at first, because you "assume $S(n)$." But you aren't assuming what you want to prove. You're proving an implication: if it holds for $n$, then it holds for $n+1$. Whether anything actually holds is the base case's job. The usual picture is a line of dominoes: the base case knocks over the first one, and the inductive step says every domino is close enough to knock over the next. Take away either one and the line stays standing.
Toggle the base case, tap a link between two dominoes to break or fix it, then press RUN. Which dominoes are guaranteed to fall?
Here is the recipe on the most famous induction proof of all.
On the Sets page, the "proof" that $|\mathcal{P}(A)| = 2^n$ hid an induction inside a "$\cdots$", and the Spicy Bonus there did it properly with exactly this recipe. Any time you see "$\cdots$" in a proof, there's an induction hiding in it.
Prove that, $\forall n \in \mathbb{N}$, $$1 + 2 + \dots + n = \frac{n(n+1)}{2}.$$
Let $S(n)$ be the statement $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.
Base case: The left side of $S(1)$ is $1$ and the right side is $\frac{1 \cdot 2}{2} = 1$. So $S(1)$ is true.
Inductive step: Suppose that $n \in \mathbb{N}$ and that $S(n)$ is true. Then $$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2} + 1\right) = \frac{(n+1)(n+2)}{2},$$ which is exactly $S(n+1)$.
Conclusion: $\forall n \in \mathbb{N}$, $S(n)$ is true. $\blacksquare$
Notice where $S(n)$ got used: it turned the first $n$ terms into $\frac{n(n+1)}{2}$ in one move. Every honest inductive step uses $S(n)$ somewhere.
The same proof works as a picture. Two copies of the staircase fill a rectangle.
Now build the inductive step yourself. First, one habit that makes it much easier.
Before you touch any algebra in the inductive step, write $S(n+1)$ down as your target. Most stuck induction proofs are stuck because nobody ever wrote down where they were trying to go. And if your inductive step never uses $S(n)$, it isn't an induction proof (or you didn't need induction).
Here's that habit in action: the goal is written at the top, and you fill in the steps that get there.
The basic recipe bends in three useful ways.
The version we've been using looks back exactly one step.
In weak induction, the inductive step proves: "$\forall n \in \mathbb{N}$, if $S(n)$ is true, then $S(n+1)$ is true."
The other version is allowed to look back as far as it likes.
In strong induction, the inductive step proves: "$\forall n \in \mathbb{N}$, if $S(m)$ is true, $\forall 1 \le m \le n$, then $S(n+1)$ is true."
Despite the names, strong induction can't prove anything weak induction can't. It just makes some inductive steps much easier to write, especially when $n+1$ depends on a case far below $n$. Here's an example that needs both strong induction and several base cases.
Prove that every integer $n \ge 12$ can be written as $n = 4x + 5y$ with $x, y \in \mathbb{Z}_{\ge 0}$. (Any postage of $12$ cents or more can be paid with $4$-cent and $5$-cent stamps.)
Let $S(n)$ be the statement "$n = 4x + 5y$ for some $x, y \in \mathbb{Z}_{\ge 0}$." We use strong induction starting at $b = 12$.
Base cases: $12 = 4 \cdot 3$, $\;13 = 4 \cdot 2 + 5 \cdot 1$, $\;14 = 4 \cdot 1 + 5 \cdot 2$, $\;15 = 5 \cdot 3$. So $S(12), S(13), S(14), S(15)$ are true.
Inductive step: Suppose that $n \ge 15$ and that $S(m)$ is true, $\forall 12 \le m \le n$. Since $12 \le n - 3 \le n$, $S(n-3)$ is true: $n - 3 = 4x + 5y$. Then $n + 1 = 4(x+1) + 5y$, so $S(n+1)$ is true.
Conclusion: $S(n)$ is true, $\forall n \ge 12$. $\blacksquare$
Why four base cases? The inductive step reaches back to $n - 3$, four steps below $n + 1$. With only $S(12)$ checked, building $13$ would need $S(9)$, which is below the starting point and was never proved. Checking $12$ through $15$ means the step only ever reaches back to cases we've already covered. (And the claim can't start any lower: $11$ can't be made from $4$s and $5$s at all.)
Watch the four base cases do their job, next to an ordinary line of dominoes.
Other stamps start somewhere else. Guess where before you look.
Try one with a different starting point.
Prove that $2^n > n^2$, $\forall n \ge 5$. Then explain why the base case can't be $n = 4$.
Proof. Let $S(n)$ be the statement $2^n > n^2$.
Base case: $2^5 = 32 > 25 = 5^2$, so $S(5)$ is true.
Inductive step: Suppose that $n \ge 5$ and that $S(n)$ is true. Then $2^{n+1} = 2 \cdot 2^n > 2n^2$. Also $n^2 - 2n - 1 = (n-1)^2 - 2 > 0$ since $n \ge 5$, so $n^2 > 2n + 1$. Therefore $2n^2 = n^2 + n^2 > n^2 + 2n + 1 = (n+1)^2$, and $2^{n+1} > (n+1)^2$, which is $S(n+1)$.
Conclusion: $S(n)$ is true, $\forall n \ge 5$. $\blacksquare$
The base case can't be $4$ because $S(4)$ is false: $2^4 = 16 = 4^2$, and $16 > 16$ fails.
Here's a fact so obvious it feels silly to write down: if you have a collection of natural numbers (at least one of them), one of them is the smallest.
Well-ordering principle. Suppose $A \subseteq \mathbb{N}$. If $A \neq \emptyset$, then $\exists n \in A$ such that $\forall m \in A, m \ge n$.
(Every non-empty subset of $\mathbb{N}$ has a smallest element.)
Proof. Consider the contrapositive (logically equivalent): $$\neg(\exists n \in A \text{ such that } \forall m \in A, m \ge n) \implies A = \emptyset.$$ Equivalently: $(\forall n \in A, \exists m \in A \text{ such that } m < n) \implies A = \emptyset$.
Suppose the statement on the left is true, and $\forall n \in \mathbb{N}$ let $S(n)$ be the statement that $n \notin A$. To show that $A = \emptyset$ is the same as showing that $\forall n \in \mathbb{N}$, $S(n)$ is true. We proceed by (strong) induction:
Base case: If $1 \in A$ then, by assumption, $\exists m < 1$ such that $m \in A$. However $A \subseteq \mathbb{N}$, so this is impossible. Therefore $1 \notin A$, so $S(1)$ is true.
Inductive step: Suppose that $n \in \mathbb{N}$ and that $S(m)$ is true, $\forall 1 \le m \le n$ ($m \notin A$, $\forall 1 \le m \le n$). If $n+1 \in A$ then, by assumption, $\exists m < n+1$ such that $m \in A$. But then it must be the case that $1 \le m \le n$, which is a contradiction. Therefore $n+1 \notin A$, so $S(n+1)$ is true.
Conclusion: $\forall n \in \mathbb{N}$, $S(n)$ is true. Therefore $A = \emptyset$. $\blacksquare$
The proof in that box uses induction to prove well-ordering. You can also prove induction using well-ordering. So which one came first? Neither: you have to take one of them on faith, as an axiom about $\mathbb{N}$, and then the other one comes free.
Why is it true? Count up from $1$: you have to bump into $A$ eventually, and the first member you bump into is the smallest one. That "count up and check each number" is induction in disguise, and it's exactly how the proof in the box goes. It proves the contrapositive: if $A$ has no smallest element, then $1 \notin A$, then $2 \notin A$, and so on, so $A$ is empty.
Here's the principle on a set where the smallest element takes a moment to find.
Let $A = \{n \in \mathbb{N} : n^2 > 50\}$. Explain why $A$ has a smallest element, then find it.
$A \subseteq \mathbb{N}$, and $A \neq \emptyset$ because $10^2 = 100 > 50$, so $10 \in A$. By the well-ordering principle, $A$ has a smallest element.
To find it, count up: $1^2, 2^2, \dots, 7^2 = 1, 4, \dots, 49$ are all at most $50$, so $1, \dots, 7 \notin A$. But $8^2 = 64 > 50$, so $8 \in A$. The smallest element of $A$ is $8$.
Notice the split: well-ordering only promised that a smallest element exists. The counting is what found it.
The proof's strategy is a search: check $1$, then $2$, then $3$, and so on. The widget below runs that search on sets you choose. It also tries a couple of sets where the search has nowhere to start.
Pick a preset or tap numbers to build your own set $A$, then press HUNT. The hunter checks one number at a time, just like the proof.
Nothing in the proof needs the search to start at $1$ specifically. It only needs somewhere to start. So the same idea works for other sets of integers.
Both versions need a bound, and both need integers.
Don't drop either hypothesis. The negative integers $\{\dots, -3, -2, -1\}$ have no lower bound and no smallest element. And over $\mathbb{R}$ the bound isn't enough: $(0, 1)$ is non-empty and bounded below by $0$, but it has no smallest element (if $t \in (0,1)$ then $\frac{t}{2}$ is smaller and still in $(0,1)$). The integers work because there's a gap of $1$ between neighbors.
Sort a few sets yourself, keeping all three hypotheses in mind.
In grade school, "$17$ divided by $5$ is $3$ remainder $2$." Here's the grown-up version, which works for negative numbers too.
The "division algorithm" isn't an algorithm. It's a theorem: it says $q$ and $r$ exist and are unique, not how to find them. Meanwhile the Euclidean algorithm, later on this page, really is an algorithm. Nobody asked me before naming these.
Division algorithm. Suppose that $a, b \in \mathbb{Z}$ and that $b \neq 0$. Then there exist unique integers $q$ (quotient) and $r$ (remainder) with $$a = qb + r, \quad \text{and} \quad 0 \le r < |b|.$$
Sketch of proof. Suppose $b > 0$. Consider the set $A = \{n \in \mathbb{Z} : a - nb \ge 0\}$. Then:
So $A$ is a non-empty set of integers that is bounded above. By the well-ordering principle (the "largest element" variation): $\exists q \in A$ such that $\forall n \in A, n \le q$.
Let $r = a - qb$. Then:
If $b < 0$, apply the $b > 0$ case to $-b$: $a = q'(-b) + r$ with $0 \le r < |-b| = |b|$, so $a = (-q')b + r$. Uniqueness is the Spicy Bonus at the bottom of the page. $\blacksquare$
The condition $0 \le r < |b|$ is the whole point. Without it, $17 = 3 \cdot 5 + 2 = 2 \cdot 5 + 7 = 4 \cdot 5 - 3$, and nobody would agree on "the" remainder. The existence proof in the box uses the "largest element" version of well-ordering from the previous section: $q$ is the largest number of hops that doesn't overshoot $a$.
On a number line, $q$ counts hops of size $|b|$ from $0$, and you keep hopping until the next hop would overshoot $a$. Whatever distance is left over is $r$. The direction of the hops comes from the signs of $a$ and $b$, and the leftover always points to the right.
What if $b = 0$? Then we'd need $a = q \cdot 0 + r$ with $0 \le r < 0$. No $r$ survives that. The theorem doesn't forbid dividing by zero to be mean. There's simply nothing there.
Drag $a$ along the line and use the buttons to change $b$ (negatives allowed). The hops show $q$, and the leftover piece is $r$.
Negative numbers are where the "always $0 \le r$" rule bites.
For $a = -17$, $b = 5$, a calculator says $-17 \div 5 = -3.4$. Chopping off the decimal gives $q = -3$, so $-17 = (-3)(5) - 2$. That remainder is negative, so it's not allowed. Round down instead: $q = -4$, and $-17 = (-4)(5) + 3$, so $r = 3$. When $b > 0$, $q$ is always $\frac{a}{b}$ rounded down, never toward zero.
All four sign combinations, side by side.
Find $q$ and $r$ for: (a) $a = 47$, $b = 6$; (b) $a = -47$, $b = 6$; (c) $a = 47$, $b = -6$; (d) $a = -47$, $b = -6$.
The remainder only depends on $|b|$ and on which way $a$ points. Flipping the sign of $b$ just flips the sign of $q$.
Before the exercise, warm up: guess $q$ and $r$, then check against the hops.
Your turn.
Find $q$ and $r$ in the division algorithm for (a) $a = -100$, $b = 7$ and (b) $a = 100$, $b = -7$.
(a) $-100 = (-15) \cdot 7 + 5$, so $q = -15$ and $r = 5$. ($q = -14$ would leave $r = -2$, which isn't allowed.)
(b) $100 = (-14)(-7) + 2$, so $q = -14$ and $r = 2$.
One more picture of the division algorithm: wrap the number line around a clock with $b$ spots. The remainder is where you stop.
When the remainder comes out to $0$, the division is exact, and that gets its own notation.
If $a, d \in \mathbb{Z}$ with $d \neq 0$, we say that $d$ divides $a$, and write $d \mid a$, if $\exists q \in \mathbb{Z}$ such that $a = qd$. Otherwise we write $d \nmid a$.
Try a few, including some strange ones.
Which are true? (a) $7 \mid 91$; (b) $91 \mid 7$; (c) $-4 \mid 28$; (d) $5 \mid 0$; (e) $1 \mid -13$; (f) $6 \mid 20$.
The vertical bar trips people up in two ways.
$d \mid a$ is a sentence (true or false), not a number. "$3 \mid 12$" means "$3$ divides $12$," which is true. "$\frac{12}{3}$" is the number $4$. Order matters too: $3 \mid 12$ is true, $12 \mid 3$ is false. And watch the edge cases: every $d \neq 0$ divides $0$ (since $0 = 0 \cdot d$), and $\pm 1$ divides everything.
Here's every divisibility fact up to $24$ at once.
Now for the two numbers you met as "GCF" and "LCM." For the rest of this section, suppose $a, b \in \mathbb{Z} \setminus \{0\}$.
There is a unique $d \in \mathbb{N}$, called the greatest common divisor of $a$ and $b$, with the following properties:
Notation: $d = \gcd(a, b)$. Abbreviations: gcd, gcf, hcf.
Here's the definition at work on numbers you already know.
Use the definition to show that $\gcd(12, 18) = 6$.
The positive divisors of $12$ are $1, 2, 3, 4, 6, 12$, and the positive divisors of $18$ are $1, 2, 3, 6, 9, 18$. The common ones are $1, 2, 3, 6$.
So $\gcd(12, 18) = 6$. ($4$ divides $12$ but not $18$, so it never gets a vote.)
Sort the divisors of a few more pairs, and watch property (ii) appear at the end.
Look at what "greatest" means in (ii). It doesn't say $e \le d$. It says $e \mid d$: every common divisor divides the gcd. That's a stronger statement (it implies $e \le d$, since both are positive), and it's the version that survives in rings, where there's often no "$\le$" to use. And why is there such a $d$ at all? Uniqueness is quick, since two gcds would divide each other and so be equal. Existence falls out of Bézout's lemma later on this page.
If you read other number theory books, watch out for a shortcut.
Many books drop the letters and write the gcd as just (a, b), so the gcd of 12 and 18 shows up as (12, 18). We always write gcd(a, b) here, because (a, b) already has two jobs: an ordered pair and an open interval. When you see a bare pair next to a divisibility bar, it's almost certainly a gcd.
Turn every divisibility around and you get the lcm.
There is a unique $l \in \mathbb{N}$, called the least common multiple of $a$ and $b$, with the following properties:
Notation: $l = \operatorname{lcm}(a, b)$. Abbreviations: lcm, lcd.
The two are tied together by one formula. For example, $\gcd(12, 18) = 6$ and $\operatorname{lcm}(12, 18) = 36$, and $6 \cdot 36 = 216 = 12 \cdot 18$.
$|ab| = \gcd(a, b) \cdot \operatorname{lcm}(a, b)$
Proof. This one is easiest with prime factorizations, from the last section of the page. Signs don't affect divisibility, so we may replace $a$ and $b$ by $|a|$ and $|b|$. Write $|a| = p_1^{a_1} \cdots p_l^{a_l}$ and $|b| = p_1^{b_1} \cdots p_l^{b_l}$ with the same list of primes (exponents of $0$ allowed). By the $\min$/$\max$ Fact in that section, $$\gcd(a, b) \cdot \operatorname{lcm}(a, b) = p_1^{\min(a_1, b_1) + \max(a_1, b_1)} \cdots p_l^{\min(a_l, b_l) + \max(a_l, b_l)}.$$ For each $i$, one of $a_i, b_i$ is the min and the other is the max, so $\min(a_i, b_i) + \max(a_i, b_i) = a_i + b_i$. The product is $p_1^{a_1 + b_1} \cdots p_l^{a_l + b_l} = |a| \cdot |b| = |ab|$. $\blacksquare$
Draw all the divisors of a number as a ladder, and gcd and lcm become "highest below" and "lowest above."
The most important special case is when the gcd is as small as it can possibly be.
$a$ and $b$ are relatively prime if $\gcd(a, b) = 1$. In that case, $|ab| = \operatorname{lcm}(a, b)$.
Being relatively prime is about the pair, not about either number on its own.
Are $8$ and $15$ relatively prime? What about $21$ and $35$?
The positive divisors of $8$ are $1, 2, 4, 8$ and those of $15$ are $1, 3, 5, 15$. The only common one is $1$, so $\gcd(8, 15) = 1$: they're relatively prime, even though neither one is prime. And $\operatorname{lcm}(8, 15) = 8 \cdot 15 = 120$.
$21 = 3 \cdot 7$ and $35 = 5 \cdot 7$ share the factor $7$, so $\gcd(21, 35) = 7$ and they are not relatively prime. Here $\operatorname{lcm}(21, 35) = \frac{21 \cdot 35}{7} = 105$.
So how do you actually compute $\gcd(a, b)$? There are two ways:
The Euclidean algorithm runs on a single observation: dividing doesn't change the gcd.
Suppose $a, b \in \mathbb{Z} \setminus \{0\}$ and write $a = qb + r$, $q, r \in \mathbb{Z}$, $0 \le r < |b|$. Then $\gcd(a, b) = \gcd(b, r)$.
(If $r = 0$, read $\gcd(b, 0)$ as $|b|$: then $b \mid a$, so $\gcd(a, b) = |b|$.)
Proof. Every common divisor of $a$ and $b$ divides $a - qb = r$, and every common divisor of $b$ and $r$ divides $qb + r = a$. So $$\gcd(a, b) \mid b, r \implies \gcd(a, b) \mid \gcd(b, r) \qquad \text{and} \qquad \gcd(b, r) \mid a, b \implies \gcd(b, r) \mid \gcd(a, b),$$ each time by property (ii) of the gcd. Two positive integers that divide each other are equal, so $\gcd(a, b) = \gcd(b, r)$. $\blacksquare$
The proof is one idea used twice: $a$, $b$, and $r$ are tied together by $a = qb + r$, so anything that divides two of them divides the third.
Use the Observation over and over. Each step swaps the pair for a smaller one with the same gcd, and you stop when the remainder hits $0$.
Euclidean algorithm. Suppose $a, b \in \mathbb{Z} \setminus \{0\}$. Compute:
$$\begin{align*} a &= q_1b + r_1, \quad q_1 \in \mathbb{Z}, \quad 0 \le r_1 < |b| \text{ (write } r_0 = |b|\text{)} \\ b &= q_2r_1 + r_2, \quad q_2 \in \mathbb{Z}, \quad 0 \le r_2 < r_1 \\ r_1 &= q_3r_2 + r_3, \quad q_3 \in \mathbb{Z}, \quad 0 \le r_3 < r_2 \\ &\vdots \\ r_{n-1} &= q_{n+1}r_n + r_{n+1}, \quad q_{n+1} \in \mathbb{Z}, \quad 0 \le r_{n+1} < r_n \\ r_n &= q_{n+2}r_{n+1}, \quad q_{n+2} \in \mathbb{Z} \text{ (stop as soon as you get a remainder of 0).} \end{align*}$$
Then $\gcd(a, b) = \gcd(b, r_1) = \gcd(r_1, r_2) = \dots = \gcd(r_n, r_{n+1}) = r_{n+1}$.
Proof. Each line is a division algorithm, so by the Observation each equals sign in the chain holds. The last one holds because $r_{n+1} \mid r_n$ (the last line has no remainder), so $\gcd(r_n, r_{n+1}) = r_{n+1}$. (If already $r_1 = 0$, the chain is just $\gcd(a, b) = \gcd(b, 0) = |b|$.)
The algorithm does stop: the remainders $r_1 > r_2 > \dots$ are integers that are at least $0$, and each nonzero one produces a strictly smaller one, so after at most $|b|$ lines one of them is $0$. $\blacksquare$
Why must it stop? The remainders $r_1 > r_2 > r_3 > \dots \ge 0$ are non-negative integers, so by well-ordering (with the bound $x = 0$) the set of remainders has a smallest element. A remainder that isn't $0$ always produces a smaller one, so the smallest remainder has to be $0$.
Watch the remainders fall, one division at a time.
The last nonzero remainder is the gcd. Here it is on two numbers you wouldn't want to factor by hand.
$a = 218683$, $b = 215221$. Compute $\gcd(a, b)$.
$$\begin{align*} a &= 1 \cdot b + 3462 &&(q_1 = 1, r_1 = 3462) \\ b &= 62 \cdot 3462 + 577 &&(q_2 = 62, r_2 = 577) \\ 3462 &= 6 \cdot 577 &&(q_3 = 6, \text{no remainder}) \end{align*}$$
Conclusion: $\gcd(a, b) = 577$.
Note: $a = 379 \cdot 577$, $b = 373 \cdot 577$, so this problem is much more difficult to do by brute force factorization.
Three lines of division beat trying to factor two six-digit numbers. That gap between "gcd is easy" and "factoring is hard" turns out to matter a lot.
Much of internet encryption (RSA) is built on that gap. Multiplying two huge primes together is fast. Factoring the product back apart is, as far as anyone knows, hopelessly slow.
See that gap for yourself: race the two methods, one division per tick.
There's also a picture of the algorithm. Start with an $a \times b$ rectangle and cut off the biggest squares you can. Each row of squares is one line of the algorithm: $q$ is how many squares fit, and the leftover strip has width $r$. Keep cutting the leftover strip the same way, and the last, smallest square has side $\gcd(a, b)$.
Choose $a$ and $b$, then press STEP to cut off the biggest squares that fit. Each cut is one line of the Euclidean algorithm.
Some pairs take more lines than others. How slow can it get?
Run it by hand once.
Use the Euclidean algorithm to compute $\gcd(1071, 462)$.
$$\begin{align*} 1071 &= 2 \cdot 462 + 147 \\ 462 &= 3 \cdot 147 + 21 \\ 147 &= 7 \cdot 21 \end{align*}$$
The last nonzero remainder is $21$, so $\gcd(1071, 462) = 21$.
Here's an important corollary. Run the Euclidean algorithm backwards and something unexpected falls out: the gcd is built from $a$ and $b$ using only addition, subtraction, and multiplication by integers.
Bézout's lemma. Suppose $a, b \in \mathbb{Z} \setminus \{0\}$ and let $d = \gcd(a,b)$. Then $\{ak + bl : k, l \in \mathbb{Z}\} = \{qd : q \in \mathbb{Z}\}$.
In particular, $\exists k, l \in \mathbb{Z}$ such that $ak + bl = d$.
Proof. Let $S = \{ak + bl : k, l \in \mathbb{Z}\}$.
A smallest positive element. Let $A = \{s \in S : s > 0\} \subseteq \mathbb{N}$. $A \neq \emptyset$, since $|a| = a \cdot (\pm 1) + b \cdot 0 \in A$. By the well-ordering principle, $A$ has a smallest element $s = ak_0 + bl_0$.
$s$ is the gcd. By the division algorithm, $a = qs + r$ with $0 \le r < s$. Then $r = a - q(ak_0 + bl_0) = a(1 - qk_0) + b(-ql_0) \in S$. If $r > 0$, then $r \in A$ and $r < s$, contradicting the choice of $s$. So $r = 0$ and $s \mid a$. The same argument shows $s \mid b$. And if $e \in \mathbb{N}$ divides both $a$ and $b$, then $e$ divides $ak_0 + bl_0 = s$. So $s$ has properties (i) and (ii) of the gcd, and $s = d$. (This is also why a gcd exists at all.)
$S \subseteq \{qd : q \in \mathbb{Z}\}$. Since $d \mid a$ and $d \mid b$, write $a = xd$ and $b = yd$. Then $ak + bl = (xk + yl)d$, a multiple of $d$.
$\{qd : q \in \mathbb{Z}\} \subseteq S$. We found $d = ak_0 + bl_0$. Then $qd = a(qk_0) + b(ql_0) \in S$. $\blacksquare$
The proof in the box never runs the Euclidean algorithm. It uses only well-ordering, the division algorithm, and the definition of the gcd: the gcd turns out to be the smallest positive number you can build as $ak + bl$. To actually find $k$ and $l$, though, run the algorithm backwards.
How to find $k, l$ such that $ak + bl = d$:
In words: solve each line for its remainder, then start from the gcd and keep substituting the line above until only $a$ and $b$ are left. (That "$\vdots$" hides an induction, which is why the proof in the box avoids it.) Back to our six-digit pair.
$a = 218683$, $b = 215221$, $\gcd(a, b) = 577$. Find $k, l$ with $ak + bl = 577$.
$$\begin{align*} &a = 1 \cdot b + 3462 &&\implies \quad 3462 = a - b \\ &b = 62 \cdot 3462 + 577 &&\implies \quad 577 = b - 62 \cdot 3462 \\ &3462 = 6 \cdot 577 \end{align*}$$
$577 = b - 62(a - b) = -62 \cdot a + 63 \cdot b$
So $\gcd(a, b) = 577 = -62 \cdot a + 63 \cdot b$.
A negative coefficient isn't a mistake. It's normal.
For positive $a$ and $b$, expect one of $k, l$ to be negative: if both were positive, $ak + bl \ge a + b$, which is far bigger than $d$. (The one exception is when one of them is $0$: if $b \mid a$, then $d = b = 0 \cdot a + 1 \cdot b$.) Also, $k$ and $l$ are not unique. Adding $\frac{b}{d}$ to $k$ and subtracting $\frac{a}{d}$ from $l$ doesn't change $ak + bl$, so $577 = 311a - 316b$ works too. Always check your answer by multiplying it out.
Here are all the pairs at once: one square for every choice of $k$ and $l$.
The set version of the lemma says something about every combination, not just one: the numbers you can build as $ak + bl$ are exactly the multiples of $d$. So you can reach $d$, and you can never reach anything that isn't a multiple of $d$. See for yourself.
Hop forward or back by $a$ or by $b$ and try to land on the target. The counter keeps track of $k$ and $l$.
The same lemma, with buckets of water instead of hops.
In group language, $\{ak + bl : k, l \in \mathbb{Z}\}$ is the smallest subgroup of $(\mathbb{Z}, +)$ containing $a$ and $b$, and Bézout says it's $d\mathbb{Z}$. Later we'll see that every subgroup of $\mathbb{Z}$ looks like $n\mathbb{Z}$, using the same well-ordering trick as the proof of Bézout's lemma.
Find a pair of coefficients yourself, then put Bézout to work in a proof.
You found $\gcd(1071, 462) = 21$ above. Find integers $k, l$ with $1071k + 462l = 21$.
Solve each line for its remainder: $147 = 1071 - 2 \cdot 462$ and $21 = 462 - 3 \cdot 147$. Then
$$21 = 462 - 3(1071 - 2 \cdot 462) = -3 \cdot 1071 + 7 \cdot 462.$$
So $k = -3$, $l = 7$. Check: $-3213 + 3234 = 21$.
Suppose $a, b, c \in \mathbb{Z} \setminus \{0\}$, $\gcd(a, b) = 1$, and $a \mid bc$. Prove that $a \mid c$.
Proof. By Bézout's lemma, $\exists k, l \in \mathbb{Z}$ such that $ak + bl = 1$. Multiply by $c$: $c = ack + bcl$. Now $a \mid ack$ (it's $a$ times $ck$), and $a \mid bcl$ (since $a \mid bc$, write $bc = ma$, so $bcl = (ml)a$). So $c = a(ck + ml)$, and $a \mid c$. $\blacksquare$
Primes are the atoms of multiplication: every integer above $1$ is built out of them in exactly one way. First, the atoms.
$1$ got kicked out of the prime club, and the definition below is careful to say $p > 1$. Why? If $1$ were prime, $6 = 2 \cdot 3$ and $6 = 1 \cdot 2 \cdot 3$ would be two different factorizations, and the theorem's "unique" would be ruined. Sorry, $1$. It's not you, it's the theorem.
A prime number is an integer $p > 1$ whose only positive divisors are $1$ and $p$.
And now the theorem the whole page has been building toward.
If $n > 1$ is an integer then there is a unique way of writing $$n = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$$ where $k \in \mathbb{N}$, $p_1 < p_2 < \dots < p_k$ are prime numbers, and $\alpha_1, \dots, \alpha_k \in \mathbb{N}$.
Existence is the last Exercise in this section. For uniqueness, it's enough to show that $n$ can't be written as a product of primes (listed with repeats, in increasing order) in two different ways.
Proof. First, the Fact just below extends to longer products: if a prime $p$ divides $q_1 q_2 \cdots q_s$, then $p \mid q_1$ or $p \mid q_2 \cdots q_s$, and repeating this (an induction on $s$) gives $p \mid q_j$ for some $j$.
Suppose some integer above $1$ has two different factorizations. By the well-ordering principle, there is a smallest such integer $n$: $$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s,$$ where the $p_i$ and the $q_j$ are primes and the two lists are different. Since $p_1 \mid q_1 \cdots q_s$, we get $p_1 \mid q_j$ for some $j$. The only positive divisors of the prime $q_j$ are $1$ and $q_j$, and $p_1 > 1$, so $p_1 = q_j$.
Cancel it from both sides: $m = \frac{n}{p_1} = p_2 \cdots p_r$ equals the product of the $q$'s with $q_j$ left out. If $m = 1$, then both sides are empty products, so both lists were just $p_1$, and they weren't different after all. If $m > 1$, the two shorter lists are still different (we removed the same prime from each), so $m$ has two different factorizations. But $m < n$, which contradicts the choice of $n$. $\blacksquare$
There are two claims in there: a factorization exists, and it's unique. Existence is a strong induction (it's an exercise below). Uniqueness, in the box, is a well-ordering argument that leans on the first of these useful facts.
Before the facts, watch uniqueness happen: split a number into primes two different ways.
Here's the fact the uniqueness proof leans on.
If $p$ is a prime number, $a, b \in \mathbb{Z}$ and $p \mid ab$, then $p \mid a$ or $p \mid b$. (not true if $p$ is not prime)
Proof. If $a = 0$ or $b = 0$, then $p$ divides it, and we're done. Otherwise $\gcd(p, a)$ is a positive divisor of $p$, so it's $1$ or $p$. If it's $p$, then $p \mid a$. If it's $1$, the second Bézout exercise (with $p, a, b$ in the roles of $a, b, c$) gives $p \mid b$. $\blacksquare$
If you did the second Bézout exercise, you've already done the hard part of that proof. Here's the fact doing its everyday job.
Suppose $b \in \mathbb{Z}$ and $7 \mid 6b$. Show that $7 \mid b$.
$7$ is prime and $7 \mid 6 \cdot b$, so $7 \mid 6$ or $7 \mid b$. But $7 \nmid 6$ (since $0 < 6 < 7$). So $7 \mid b$.
For instance, $7 \mid 6 \cdot 35 = 210$, and sure enough $35 = 5 \cdot 7$.
That parenthetical "not true if $p$ is not prime" is worth a concrete example too.
$6 \mid 4 \cdot 9 = 36$, but $6 \nmid 4$ and $6 \nmid 9$. The $2$ in $6$ came from the $4$ and the $3$ came from the $9$. A prime can't be split up like that, which is exactly why the fact needs $p$ to be prime.
Try to break the fact yourself. It's easy for some $n$ and impossible for others.
The second fact turns gcd and lcm into a comparison of exponents. Suppose that $p_1 < p_2 < \dots < p_l$ are primes and that $$\begin{align*} a &= p_1^{a_1}p_2^{a_2}\dots p_l^{a_l}, \quad a_1, \dots, a_l \ge 0, \\ b &= p_1^{b_1}p_2^{b_2}\dots p_l^{b_l}, \quad b_1, \dots, b_l \ge 0. \end{align*}$$ (Exponents of $0$ are allowed, so both numbers can use the same list of primes.)
Proof. (i) Let $d = p_1^{\min(a_1, b_1)} \cdots p_l^{\min(a_l, b_l)}$. Each exponent of $d$ is at most the matching exponent of $a$ and of $b$, so $d \mid a$ and $d \mid b$. Now suppose $e \in \mathbb{N}$ divides both, say $a = ec$. Any prime dividing $e$ divides $a$, so (by the Fact above, extended to longer products) it is one of $p_1, \dots, p_l$. Write $e = p_1^{e_1} \cdots p_l^{e_l}$. Factoring $c$ too, $a = ec$ gives a factorization of $a$ in which $p_i$ appears at least $e_i$ times, so by uniqueness $e_i \le a_i$. In the same way $e_i \le b_i$. So $e_i \le \min(a_i, b_i)$ for every $i$, and $e \mid d$. So $d$ has both properties of the gcd.
(ii) Let $t = p_1^{\max(a_1, b_1)} \cdots p_l^{\max(a_l, b_l)}$. Then $a \mid t$ and $b \mid t$. If $a \mid m$ and $b \mid m$: when $m = 0$, $t \mid m$. Otherwise the same uniqueness argument shows $p_i$ appears in the factorization of $|m|$ at least $a_i$ times and at least $b_i$ times, so at least $\max(a_i, b_i)$ times, and $t \mid m$. So $t$ has both properties of the lcm. $\blacksquare$
On ISEE Section 0, the GCF of $12$ and $18$ was "the primes they share" and the LCM was "every prime either one needs." Those were $\min$ and $\max$ all along.
Here's one worked all the way through.
Find $\gcd(360, 84)$ and $\operatorname{lcm}(360, 84)$.
Factor, using the primes $2, 3, 5, 7$ for both: $360 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^0$ and $84 = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1$.
$\gcd(360, 84) = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^0 = 12$
$\operatorname{lcm}(360, 84) = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1 = 2520$
Check: $12 \cdot 2520 = 30240 = 360 \cdot 84$.
That check is no accident. For each prime, $\min(a_i, b_i) + \max(a_i, b_i) = a_i + b_i$ (one of them is the min and the other is the max). So multiplying the gcd by the lcm uses exactly the same exponents as $ab$. That's the whole proof of $|ab| = \gcd(a, b) \cdot \operatorname{lcm}(a, b)$ from the gcd section. Stack the primes and watch it happen.
Use the arrows to change $a$ and $b$. Each column is one prime, stacked once per factor. The gcd takes the shorter stack in each column, and the lcm takes the taller one.
Two to finish the section: one computation and one proof.
Let $a = 2^4 \cdot 3 \cdot 5^2$ and $b = 2 \cdot 3^3 \cdot 7$. Find $\gcd(a, b)$ and $\operatorname{lcm}(a, b)$. Are $a$ and $b$ relatively prime?
Write $a = 2^4 \cdot 3^1 \cdot 5^2 \cdot 7^0$ and $b = 2^1 \cdot 3^3 \cdot 5^0 \cdot 7^1$.
$\gcd(a, b) = 2^1 \cdot 3^1 = 6$ and $\operatorname{lcm}(a, b) = 2^4 \cdot 3^3 \cdot 5^2 \cdot 7 = 75600$.
They are not relatively prime, since the gcd is $6$, not $1$. (Check: $a = 1200$, $b = 378$, and $6 \cdot 75600 = 453600 = 1200 \cdot 378$.)
Prove the existence half of the FTAr: every integer $n > 1$ is a product of primes. (A prime by itself counts as a product of one prime.)
Proof. Let $S(n)$ be the statement "$n$ is a product of primes." We use strong induction starting at $b = 2$.
Base case: $2$ is prime, so $S(2)$ is true.
Inductive step: Suppose that $n \ge 2$ and that $S(m)$ is true, $\forall 2 \le m \le n$. If $n + 1$ is prime, $S(n+1)$ is true. Otherwise $n+1$ has a positive divisor $c$ with $1 < c < n+1$, so $n + 1 = cd$ with $1 < c, d < n + 1$. Then $2 \le c, d \le n$, so $S(c)$ and $S(d)$ are true. Multiplying the two products of primes gives $n + 1$ as a product of primes, so $S(n+1)$ is true.
Conclusion: $S(n)$ is true, $\forall n \ge 2$. $\blacksquare$
This is why we needed strong induction: $c$ and $d$ can be anywhere between $2$ and $n$, not just equal to $n$.
Every question below makes a new version each time you press the button, in the same order as the lesson. Every wrong choice is a real mistake, and choosing one tells you which.
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
The division algorithm promised unique $q$ and $r$, and so far we've only proved they exist. Time to pay that off. The key is that $r$ is trapped in a window narrower than $|b|$.
Suppose $a, b \in \mathbb{Z}$, $b \neq 0$, and $a = qb + r = q'b + r'$ with $q, q', r, r' \in \mathbb{Z}$, $0 \le r < |b|$, and $0 \le r' < |b|$. Prove that $q = q'$ and $r = r'$.
Proof. Subtracting the two expressions for $a$ gives $(q - q')b = r' - r$.
Both $r$ and $r'$ lie in $[0, |b|)$, so they are less than $|b|$ apart: $|r' - r| < |b|$. Therefore $|q - q'| \cdot |b| = |r' - r| < |b|$, and dividing by $|b| > 0$ gives $|q - q'| < 1$.
But $q - q'$ is an integer, and the only integer with absolute value less than $1$ is $0$. So $q = q'$, and then $r' - r = (q - q')b = 0$, so $r = r'$. $\blacksquare$