1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How old is your child? $\endgroup$ – Amy B Sep 7 at 8:46
  • $\begingroup$ It should be in the question - because you usually explain things differently to a 7 year old than you would to a 3 year old, a 15 year old, or a 20 year old. $\endgroup$ – Amy B Sep 7 at 15:12
  • $\begingroup$ @AmyB thanks, question updated. $\endgroup$ – athos Sep 7 at 16:52
  • $\begingroup$ Are you looking for a proof of en.wikipedia.org/wiki/Bezouts_identity which does not use continued fractions, or one which does? If you are looking for one which avoids continued fractions, the wikipedia article works. You might also gain inspiration from Marty Weissman's "Illustrated Theory of Numbers". $\endgroup$ – Steven Gubkin Sep 8 at 16:57
  • 2
    $\begingroup$ If you shoot me an email, I'll send you a few relevant pages from my Illustrated Theory of Numbers book, with the "hop and skip" approach to Bezout. Cheers, Marty Weissman. (I'm easy to find online... at UC Santa Cruz) $\endgroup$ – Marty Sep 10 at 4:34
4
+200
$\begingroup$

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*} $$

| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ I don't know who gave this -1, but if you are going to do that you need to explain why so that the answer can be improved. $\endgroup$ – Chris Cunningham Sep 8 at 19:37
  • $\begingroup$ It would be an interesting experiment to require an anonymous explanation when giving a -1. We must click a reason to flag an answer (to help the moderators decide what to do), so forcing this kind of thing with voting would be a great improvement to the process (to help answers/authors decide what to do). $\endgroup$ – Nick C Sep 8 at 19:47
  • 1
    $\begingroup$ Indeed. This question was probably a better math.stackexchange question than a question for this site, and my answer is brief, but I think it contains everything a skilled educator who was looking for a path through the material would need to devise a suitable explanation for their student. $\endgroup$ – Steven Gubkin Sep 8 at 19:56
  • 1
    $\begingroup$ i didn't vote it down. yes this is the standard Euclidean algorithm to get Bézout's identity, though I wished for something more graceful. $\endgroup$ – athos Sep 8 at 20:17
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! Of course you are right on $(-1)^{s-1}$, question updated. I'm walking along with my kid along the way, combining Steven, Marty and yours suggestions. I'll answer the question when we finished the lovely journey. $\endgroup$ – athos Sep 19 at 17:08
0
$\begingroup$

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:

enter image description here

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

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:

enter image description here

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.

enter image description here

Then we are done.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.