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.
