## coprime numbers; constructing a regular n-gon

### Task number: 2802

Show by induction that for every two coprime (i.e. relatively prime) natural numbers \(m\) and \(n\) there exist integers \(x\) and \(y\) such that \(mx+ny=1\).

As a consequence, show that if it is possible to construct a regular \(m\)-gon and a regular \(n\)-gon with a compass and straightedge, then with the same instruments it is also possible to construct a regular \(mn\)-gon.

#### Hint

Recall Euclid's algorithm for finding the greatest common denominator of two numbers.

#### Resolution

If \(m\) and \(n\) are relatively prime and \(m>n\), then \(m-n\) is relatively prime to \(n\).

If we proceed by induction on the sum \(m+n\), the inductive assumption is valid for the pair \(m-n\) and \(n\), so there exist \(x'\) and \(y'\) such that \((m-n)x'+ny'=1\).

It follows that \(mx'+n(y'-x')=1\), so the coefficients we are seeking are \(x=x'\) and \(y=y'-x'\).

We must verify the first inductive step for the pair \((2, 1)\), for which the desired coefficients are \(x=1\), \(y=-1\).

To construct a regular \(mn\)-gon we assume without loss of generality that \(x\) is positive and \(y\) is negative. If we construct regular \(m\)- and \(n\)-gons so that they are inscribed in the same circle and have a common vertex \(A_0=B_0\), then the segment \(A_xB_{-y}\) is a side of a regular \(mn\)-gon inscribed in the same circle.