## coprime numbers; constructing a regular n-gon

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.  