タイル貼り再び…今度はユークリッド互除法を試してみよう
「タイル貼りの技術がいいという評判で別の注文がきました。
問．今度の壁は245cmと173cmです。このときの最大の正方形のタイルのサイズは？
これは、先ほどの問題と同じですから245と173の最大公約数を求める問題です。そこでユークリッド互除法を使ってみましょう。
いま、245と173の最大公約数をnとします。
245を173で割ります。商が1で余りが72になります。
245=173×1+72
→ 72 = 245 − 173 × 1なので、72はnで割り切れます。こうして、最大公約数nは245, 173, 72の公約数になります（＊1）。
173を72（余り）で割ります。商が2で余りが29になります。
105=70×1+35
→29=173−72×2であり、（＊1）より、最大公約数nは173, 72の約数なので、29の約数にもなります。こうして、最大公約数nは、245, 173, 72, 29の約数になります（＊2）。
72を29（余り）で割ります。商が2で、余りは14です。
72=29×2+14
→ 14 = 72 − 29 × 2であり、（＊2）より、最大公約数nは72, 29の約数なので、14の約数にもなります。こうして、最大公約数nは245, 173, 72,29, 14の約数になります（＊3）。
29を14（余り）で割ります。商が2、余りが1です。
29=14×2+1
→ 1 = 29 − 14 × 2であり、（＊3）より、最大公約数nは29, 14の約数なので、1の約数にもなります。しかし、最大公約数nが1の約数になるというこ
とは、n = 1ということにほかなりません。
こうして、245, 173の最大公約数は1ということです。
つまり、この壁は1cmの正方形タイルでしか貼れないということになります。
今回は、1cmの正方形タイルでしか貼れなかった photo by gettyimagesここでわかることは、このプロセスで4. のように余り1が出てきた場合には、二つの数の最大公約数は1になるということです。このプロセスはここで終わりです。
二つの数の最大公約数が1となる場合に、この二つの数は互いに素であるといいます。
245と173は公約数が1しかない、互いに素な数であった
ということです。
二つの数の公約数を求めるには素因素分解すればよいのですが、それが大変な場合はユークリッド互除法の方が簡単で確実です。
それだけではなく、ユークリッド互除法を用いて最大公約数を求める方法からは、数の理論（数論）において基本的で重要な副産物がもたらされるのです。
＊こちらの続きは、6月27日（木）公開予定です。
NEXT 〉 小学生の素朴な疑問が鋭すぎる…数論における基本的で重要な副産物を突いた
