M@X — Math Circles (Spring 2026) • Week 5

Typed version (MathJax)

This section follows the Week 5 notes in order. The full original notes appear below, page by page.

Problem: the simplest fraction between two fractions

We begin with the problem of finding the simplest fraction between two given fractions. The first example is

\[ \frac{11}{18} < ? < \frac{7}{11}. \]

We solve this by locating both fractions on the Stern–Brocot tree and taking their last common ancestor. The answer shown is

\[ \frac{11}{18} < \frac{5}{8} < \frac{7}{11}. \]

Cross-multiplication confirms it: \[ 88 < 90,\qquad 55 < 56. \]

A second example using overlap

Then we ask what happens between \(\tfrac{11}{18}\) and \(\tfrac{5}{8}\).

Using Stern–Brocot paths, we write

\[ \frac{11}{18} = LRLRLL, \qquad \frac{5}{8} = LRLRLR^\infty. \]

Since we may append \(R^\infty\) or \(L^\infty\) without changing the represented number, the longest overlap is

\[ LRLRL = \frac{8}{13}. \]

So we conclude

\[ \frac{11}{18} < \frac{8}{13} < \frac{5}{8}, \] with \[ 143 < 144,\qquad 64 < 65. \]

Another example with nearest common ancestor

The next example asks for a fraction between

\[ \frac{6}{11} < ? < \frac{8}{13}. \]

We record the Stern–Brocot descriptions \[ \frac{6}{11} = LRLLLL, \qquad \frac{8}{13} = LRLRL, \] and identify the nearest common ancestor \[ LRL = \frac35. \]

Hence

\[ \frac{6}{11} < \frac35 < \frac{8}{13}, \] checked by \[ 30<33,\qquad 39<40. \]

A number-theoretic fact

We now switch to a Diophantine equation viewpoint. If two integers such as \(12\) and \(17\) have no common factors, then we can solve

\[ 17x - 12y = 1 \]

using whole numbers. One example given is

\[ 17(17) - 12(24) = 289 - 288 = 1. \]

But this is not the smallest solution, since

\[ 17(5) - 12(7) = 85 - 84 = 1. \]

Problem: find the best (smallest) solution

We ask:

Problem. How do we find the best, meaning the smallest, solution?

The answer given is: find \(\tfrac{12}{17}\) on the Stern–Brocot tree; then its NDA gives the best solution.

\[ \text{NDA}=\frac57. \]

Then \[ 12(7)=84,\qquad 5(17)=85, \] so \[ 5(17)-12(7)=1. \]

Example: \(\frac{80}{63}\)

The last two pages work out the same idea for \(\tfrac{80}{63}\). First we express it as a continued fraction:

\[ \frac{80}{63} = 1 + \frac{17}{63} = 1 + \frac{1}{\frac{63}{17}} = 1 + \frac{1}{3 + \frac{12}{17}} = [1;3,1,2,2,2]. \]

We then translate this into a Stern–Brocot path:

\[ [1;3,1,2,2,2] \longleftrightarrow R^3LRL^2R^2L. \]

The NDA is obtained by removing the last block, plus one more letter, giving

\[ R^3LRL^2R \quad\leftrightarrow\quad [1;3,1,2,2]. \]

Computing the NDA fraction

We evaluate

\[ [1;3,1,2,2] = \frac{33}{26}. \]

Therefore the best solution is given by

\[ \frac{80}{63},\qquad \frac{33}{26}, \] and indeed \[ 80(26)-63(33)=2080-2079=1. \]

Main idea

Week 5 ties together two viewpoints:

the Stern–Brocot tree and continued fractions for finding the simplest fraction between two others,
the same machinery for finding the smallest positive integer solution to equations of the form \[ ax-by=1 \] when \(a\) and \(b\) are relatively prime.

The key recurring object is the nearest distant ancestor (NDA).