How can I explain construction of the Bézout's identity to my kid?

Question

My kid is soon 7 years old, he could understand fractions, linear equation and modulo operation. I've just taught him Chinese remainder theorem, looking to introduce some more basic number theory stuff.

One of the topics sound interesting is the Euclidean algorithm, together with the Bézout's identity :

Given two coprime numbers $m$ and $n$, i.e. $(m,n)=1$, there exist $P$ and $Q$ such that $$ Pm-Qn=1$$. The explicit construction of Bézout's identity can be done via continued fraction that if $$\frac{m}{n}=[a_0;a_1,\dots,a_s],$$ then $$\frac{Q}{P}=(-1)^{s-1}[a_0;a_1,\dotsc,a_{s-1}].$$

This construction method could be proved using Continued fraction's properties. However, I'm afraid this is a bit too much to my kid, with 2 sequences, and algebra manipulation.

Is there a way I could adopt to prove it, using a simpler approach? Or is there another way to construct Bézout's identity, without continued fraction but also easy to understand?

Answer 1

I will answer with an example. I seek the Bezout coefficients for 99 and 707.

First I execute the Euclidean algorithm:

$$ \begin{align*} 707 &= 7 \cdot 99+14\\ 99 &= 7 \cdot 14+ 1 \end{align*} $$

Now, I will recursively "backtrack"

$$ \begin{align*} 1 &= 99-7\cdot 14\\ &= 99-7 \cdot (707-7 \cdot 99)\\ &=50 \cdot 99 - 7 \cdot 707 \end{align*} $$

Answer 2

Simplest explanation I've seen is to take $a, b$ integers and consider the set $\{u a + v b\}$ for integer $u, v$. It is a bunch of integers, so it has to contain a smallest positive one, call it $d = u_0 a + v_0 b$.

Now divide $a$ by $d$: $a = q d + r$, by the Euclidean "algorithm" $0 \le r < d$. You see that:

$\begin{align*} a &= (u_0 a + v_0 b) q + r \\ r &= (1 - q u_0) a - q v_0 b \end{align*}$

Thus $r$ belongs to our set, is non-negative, and is smaller than it's smallest positive element $d$. Only possible value is $r = 0$. You can repeat the same argument for $b$, so that $d \mid a$ and $d \mid b$.

Now any number that divides both $a$ and $b$ must also divide $d = u_0 a + v_0 b$, i.e., $\gcd(a, b) \mid d$.

Now suppose $c$ is a common divisor of $a$ and $b$, this means:

$\begin{align*} a &= c x_0 \\ b &= c y_0 \\ d &= u_0 x_0 c + v_0 y_0 c \\ &= (u_0 x_0 + v_0 y_0) c \end{align*}$

So any such $c$ divides $d$, $d$ is largest possible.

Answer 3

Probably you know all of the following, but just to have it on the record:

Most seven year olds are not fluent with fractions, but if you have one that is especially skillful in manipulating them, he might be able to learn how to relate the Euclidean algorithm to the continued fraction, learn to manipulate continued fractions and to understand their properties, and eventually—but this may take a while—to see how the Bézout coefficients come out of the continued fraction. It all depends on whether he manages to stay interested during the process, which could be a lengthy one. Continued fractions are fascinating objects in their own right, and well worth learning about.

Before proceeding, I wanted to mention that there seems to be a factor of $(-1)^{s-1}$ missing in your expression for $\frac{Q}{P}$.

Let's show that the $\gcd$ of $6186$ and $3014$ is $2$, with the continued fraction and standard Euclidean algorithm shown side-by-side: \begin{align} \frac{6186}{3014}&=2+\frac{158}{3014} & & 6186=2\cdot3014+158\\ &=2+\frac{1}{19+\frac{12}{158}} & & 3014=19\cdot158+12\\ &=2+\frac{1}{19+\frac{1}{13+\frac{2}{12}}} & & 158=13\cdot12+2\\ &=2+\frac{1}{19+\frac{1}{13+\frac{1}{6+\frac{0}{2}}}} & & 12=6\cdot2+0.\\ \quad \end{align}

Computing the convergents by brute force—we'll do it in a better way in a second—gives $$ 2=\frac{2}{1},\quad 2+\frac{1}{19}=\frac{39}{19},\quad 2+\frac{1}{19+\frac{1}{13}}=\frac{509}{248},\quad 2+\frac{1}{19+\frac{1}{13+\frac{1}{6}}}=\frac{3093}{1507}=\frac{6186}{3014}. $$ Now for the better way. Evaluating the third convergent as an example, and keeping focus on the dependence of the convergent on the third term in the continued fraction, which has value $13$ here, we see that $$ 2+\frac{1}{19+\frac{1}{13}}=2+\frac{13}{19\cdot13+1}=\frac{2(19\cdot13+1)+13}{19\cdot13+1}=\frac{39\cdot13+2}{19\cdot13+1}. $$ We observe that

1. the dependence on the parameter $13$ is of the form $x\mapsto\frac{ax+b}{cx+d}$;
2. the integer coefficients are derived from the previous two convergents, $\frac{39}{19}$ and $\frac{2}{1}$.

These features are true of all convergents, and it's not hard to understand why. Let's compute the fourth convergent by modifying the third convergent. The term $13$ needs to be replaced by $13+\frac{1}{6}$: $$ \frac{39\left(13+\frac{1}{6}\right)+2}{19\left(13+\frac{1}{6}\right)+1}=\frac{(39\cdot13+2)\cdot6+39}{(19\cdot13+1)\cdot6+19}, $$ confirming that the dependence on the fourth term, $6$, is of the expected form, with coefficients given by the previous two convergents.

To follow this, of course, your son would have to be very comfortable with dividing fractions, using the distributive, commutative, and associative laws, and things like that, which, in my experience, would be extremely rare in a seven year old. But this method avoids algebra, and I think is still convincing. I chose the numbers so that the terms in the continued fraction would be distinctive, allowing you to watch how they move around in the calculation, but you could choose more tractable numbers, and repeat the calculation on several small examples to make the same points.

Continuing on, note that since $$ 2+\frac{1}{19}=\frac{2\cdot19+1}{1\cdot19+0}, $$ and since $$ 2=\frac{1\cdot2+0}{0\cdot2+1}, $$ the pattern of convergents can be continued backwards, with the same rule applying, to get $$ \frac{0}{1},\quad\frac{1}{0},\quad\frac{2}{1},\quad\frac{39}{19},\quad\frac{509}{248},\quad\ldots, $$ where the initial two convergents have the same values for every continued fraction.

The next thing to learn is what happens when you cross multiply successive convergents and take the difference. Considering the convergents $$ \frac{39}{19},\quad\frac{509}{248}=\frac{39\cdot13+2}{19\cdot13+1},\quad\frac{3093}{1507}=\frac{(39\cdot13+2)\cdot6+39}{(19\cdot13+1)\cdot6+19}, $$ compute \begin{align} &3093\cdot248-1507\cdot509\\ &\quad=\left[(39\cdot13+2)\cdot6+39\right]\left(19\cdot13+1\right) - \left[(19\cdot13+1)\cdot6+19\right]\left(39\cdot13+2\right)\\ &\quad=39\cdot(19\cdot13+1)-19\cdot(39\cdot13+2)=39\cdot1-19\cdot2=1\\ &\quad=-\left[(39\cdot13+2)\cdot19-(19\cdot13+1)\cdot39\right]\\ &\quad=-\left[509\cdot19-248\cdot39\right]. \end{align} Examining this calculation should convince you that the difference of cross multiplications alternates in sign and has value $\pm1$ for every pair of successive convergents. This implies, by the way, that the convergents must be fractions reduced to lowest terms, since any factor common to the numerator and denominator would be common to both terms in the expression above, and would therefore divide $1$.

Now if you rewrite the final convergent, $\frac{3097}{1507}$, as $\frac{6186}{3014}$, you see how the $\gcd$ (up to a possible minus sign) comes about by cross multiplying and subtracting it with the second-to-last convergent.

Answer 4

Just to record what my kid and me went through.

First of all, thank you everyone for the great ideas and help!

We started from Euclidean Algorithm, explained by folding an A4 paper again and again:

Then following the classic way, as Steven showed, to rely on Euclidean Algorithm's steps to derive Bézout's Identity:

Just as Will said, this has to go through "dividing fractions, using the distributive, commutative, and associative laws", it took him a while to see things such as $a-(b-c)d=a-bd+cd$, $ax-by+az=a(x+z)-by$, but it's a good practice.

Also it took him quite some time to understand the substitution -- he preferred to compute things out instead of keep the $a$ and $b$ to reach the $ax+by$ form.

Then it's to show that continued fraction actually can serve as a short form of Euclidean Algorithm steps, basically they are all different ways to tell the same story:

Last it's to show that the continued fraction form from Euclidean Algorithm, after removing the inner most part, actually is just the one to compute Bézout's Identity. Or, bottom up, the Bézout's Identity $x$ and $y$ are driven by the same mechanism driving $a$ and $b$.

This logic is mentioned by Will and Marty ("hop and skip" in ch 1 of his fabulous book An Illustrated Theory of Numbers), also by David C Garlock (in ch 3 of his number theory book), and Andrew Granville ( in Appendix 1A. "Reformulating the Euclidean algorithm" of his book Number Theory Revealed - A Master Class, very clear, but, alas, used matrix).

By adopting ideas I drew a somewhat "tree" style diagram (it's not tree, but i don't know how to describe such shape) to represent the continued fraction, and a "simple tree" to only remark the driving force of the "tree", then it's shown that the two continued fractions are the same except the inner most part.

Then we are done.