Bezout's Theorem

Question

I have seen the proof of Bezout's theorem via the use of strong induction. \medskip

The theorem states the following; Let $a$ and $b$ $\in \mathbb{Z}.$ Then there exists $m$, $n$ $\in \mathbb{Z}$ such that; $$gcd(a,b) = a(m) + b(n).$$

The proof starts with two base cases $r_0$ and $r_1$, where $r_i$ are the remainder terms.

What I'm struggling to understand is why are two base cases necessary for the proof, and why is $r_0 = b?$

I find that I understand the proof line by line but I'm struggling conceptually with the proof.

Answer 1

This can be proved easily using the fact that any non-empty subset of the natural numbers has a least element (avoiding any difficulty you might have with induction).

For fixed $a$ and $b$ in $\mathbb{N}$ let $k=am+bn$ be least non-negative element in the set $S=\{ax+by\,|\,x,y\in \mathbb{Z}\}$ (i.e. the least element in $T=\{s\,|\, s\in S, s>0\}$). Suppose $k'=am'+bn'$ is a positive element in $S$. According to the Euclidean algorithm there are $l$ and $r$ where $r\in\{0,..,k-1\}$ such that $k'=kl+r$. This means that $r=am'+bn' - (am+an)l=a(m'-ml)+b(n'-nl) \in S$ and hence $r=0$ (since $r< k$). We have proved that $k\vert k'$ for any $k'\in S$ where $k' >0$. Since $a$ and $b$ are in $S$ it follows that $k \vert a$ and $k \vert b$. However if $x\vert a$ and $x\vert b$ then $x \vert am+bn=k$. This means that $k$ is the greatest common divisor of $a$ and $b$.

Answer 2

I'm not sure what you mean by $r_0$ and $r_1$ and $r_i$.

But the usual proof of this theorem by strong induction starts with the base cases $b=0$ and $b=1$, so I'm guessing this is what you found strange.

And it is a little strange, but really harmless. Let me explain.

Suppose you want to prove something by induction for all $b=0,1,2,\dots$ Typically you would prove a base case $b=0$, and then prove that if the claim is true for any $b$, it is also true for $b+1$.

Now strong induction is a little different, as you know. Typically you would prove a base case $b=0$, and then prove that is the claim is true for any $b'$ such that $0\le b' < b$, then it is also true for $b$. Strong induction is called "strong", because you're allowed to use many earlier cases at the same time, and not just the previous one. For example, if you want to prove the claim for $b=5$, normal induction only lets you assume that the case $b=4$ is already proved, while strong induction allows you to use all of $b=0,1,2,3,4$ as proved. So it's a stronger tool, it gives you more power "for free".

Now back to base cases. It often happens that when we want to prove some claim for all possible values, the first few numbers are both easy and "different". For example, the base case in induction is usually pretty easy. But often not just the base case, but the one after it is also very easy. And it may be that it still feels "special", not "generic" enough. So, because it's easy to prove it directly and not by using an induction hypothesis, people just prove it directly. There's no harm in it.

So it is with Bezout's theorem. The case $b=0$, the base case, it very easy, because $gcd(a,0)=a$, and we easily see how to find the necessary $m,n$. The case $b=1$ is also very easy, because $gcd(a,1)=1$, and again we see immediately how to find $m,n$. We don't even need to use the case $b=0$ to prove the case $b=1$. So we just prove it directly and call it also a "base case".

But from $b=2$ on it looks more complicated and we don't know what to do. So we use the general argument, using the division algorithm: $a=qb+r$, where $0\le r < b$, and now we apply the induction hypothesis to the pair $(b,r)$. If $r=0$ or $r=1$, that's one of our base cases, and other values of $r$ can be assumed proven by induction hypothesis. It's really not a problem that we'd proved $b=1$ directly as a base case. Who cares, as long as we can rely on it being true.

Actually, if you think about it, we didn't need to prove $b=1$ as a base case. The general induction argument we have used for $b$ starting with $2$ will also work for $b=1$. You can apply the division algorithm to $(a,b)$ when $b=1$, and you will get $a=qb+r$ in the form $a=a*1+0$, that is, $q=a$ and $r=0$ necessarily. Then you continue as in the normal proof, which already handles the case $r=0$. It's not a problem.

So why didn't we do it this way? Well, it's a psychological thing. It feels weird to apply the division algorithm when you divide by $1$. It's a degenerate case, sort of. It all works out according to all the formulas, but it feels more straightforward to just prove the case $b=1$ directly. It's a matter of preference. We could only prove $b=0$ as a base case, and use the general argument for all other $b$'s. But in that case, someone reading the proof later would still want to check mentally that it makes sense at the weird "edge case" when $b=1$. So it's not like we'd be making the proof clearer. The proof would be shorter but arguably harder to trust, because when reading it you'd go "hmm, they're dividing by $b$ for all values $b\ge 1$... wouldn't they get something weird dividing by $1$ since that's not really a division and nothing changes? I'd better follow that case mentally".

So this is why people sometimes prove more than one base cases outright, directly. To start off the induction and to handle the weird non-generic cases before handling the general case.