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?

  • $\begingroup$ How old is your child? $\endgroup$
    – Amy B
    Sep 7, 2020 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, 2020 at 15:12
  • $\begingroup$ @AmyB thanks, question updated. $\endgroup$
    – athos
    Sep 7, 2020 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$ Sep 8, 2020 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, 2020 at 4:34

5 Answers 5


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

  • 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$ Sep 8, 2020 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, 2020 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$ Sep 8, 2020 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, 2020 at 20:17

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.


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.

  • $\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, 2020 at 17:08

"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?"

Your question is two years' old so this may be untimely but there is an algorithm that operates on two natural numbers p and q which in a single process and using just addition and subtraction will provide gcd(p, q), Bezout identity, expression of non-coprime p and q as a fraction in lowest form, continued fraction terms (with some simple interpretation) and successive approximations.

A: 31 (1) - 13 (0) = 31 First chosen starting number

B: 31 (0) - 13 (1) = -13 Second chosen starting number multiplied by -1

C = A + B: 31 (1) - 13 (1) = 18

Add the smallest positive result obtained so far to the 'smallest' negative result so far - 'smallest' here meaning 'closest to zero'

D = B + C 31 (1) - 13 (2) = 5

Repeat the above operation: add smallest negative to smallest positive and add to list

E = B + D: 31 (1) - 13 (3) = -8 Repeat above instructions

F = D + E: 31 (2) - 13 (5) = -3

G = D + F: 31 (3) - 13 (7) = 2

H = F + G: 31 (5) - 13 (12) = -1

I = G + H: 31 (8) - 13 (19) = 1

J = H + I: 31 (13) - 13 (31) = 0

The gcd is the smallest non-zero result (1) which in this algorithm will always appear once as negative and once as positive value. The Bezout identity is seen from the co-efficients of the equation resulting in the gcd. If the starting numbers are not co-prime then the co-efficients of the final equation that equals zero will represent the starting numbers as a fraction in lowest form. The successive approximations to 13 / 31 or its inverse are seen from the co-efficients of the equations as the alorithm progresses. These pairs also represent the route down the Stern-Brocot tree to 13 / 31.

The continued fraction is not as obvious as in the Euclidean algorithm. It is shown by the pattern of flipping of signs from positive to negative and back again, disregarding the first two equations for the starting numbers. In this example the results are +18, +5, -8, -3, +2, -1, +1, 0. Two positives, two negatives, one positive, one negative, and finally one positive and zero which is counted as whichever sign the term before it has. So the continued fraction is [2; 2, 1, 1, 2] or [0; 2, 2, 1, 1, 2], since the algorithm is identical for a fraction and its inverse.

A slightly more sophisticated version of the algorithm, using the floor values of division rather than just repeated subtraction, gives a neater route to the continued fraction. For larger numbers this is necessary.

The method is equivalent to using matrix multiplication but matrices are not needed explicitly. I can say that it's easy and quite a lot of fun.

More explanation about how this works https://simplyfractions.blogspot.com/p/blog-page_5.html


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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