Nesoudělná čísla; konstrukce n-úhelníku
Úloha číslo: 2794
Dokažte indukcí, že pro každá dvě nesoudělná přirozená čísla \(m\) a \(n\) existují celá čísla \(x\) a \(y\), že \(mx+ny=1\).
Jako důsledek ukažte, že lze-li zkonstruovat pravítkem a kružítkem pravidelný \(m\)-úhelník a pravidelný \(n\)-úhelník pro nesoudělaná \(m\) a \(n\), potom lze stejnými nástroji zkonstruovat i pravidelný \(mn\)-úhelník.
Nápověda
Vzpomeňte si na Eukleidův algoritmus pro hledání největšího společného dělitele.
Řešení
Jsou-li \(m\) a \(n\) nesoudělná a \(m>n\), potom \(m-n\) je nesoudělné s \(n\).
Postupujeme-li indukcí podle součtu \(m+n\), platí indukční předpoklad pro dvojici \(m-n\) a \(n\), tedy existují \(x'\) a \(y'\) taková, že \((m-n)x'+ny'=1\).
Z toho plyne, že \(mx'+n(y'-x')=1\), tedy hledané koeficienty jsou \(x=x'\) a \(y=y'-x'\).
První krok indukce je třeba ověřit pro dvojici \((2{,}1)\), pro níž hledané koeficienty jsou \(x-1\), \(y=-1\).
Pro konstrukci \(mn\)-úhelníku předpokládejme bez újmy na obecnosti, že \(x\) je kladné, zatímco \(y\) je záporné. Pokud zkonstruujeme \(m\)- a \(n\)-úhelníky tak, že jsou vepsané stejné kružnici a mají vrchol \(A_0=B_0\) společný, potom úsečka \(A_xB_{-y}\) je hranou \(mn\)-úhelníku vepsaného téže kružnici.