数学一人旅２　　整数方程式

「abc予想」が証明されて話題になりましたが、整数論の世界は一見単純に見えることがとても難解な世界です。比較的わかりやすい整数論の問題を１つ紹介します。現役の高校生は数Aで扱う内容です。

問題 $\ \ \ \$ 横95m縦28mの床をできるだけ大きな正方形のタイルで敷き詰めるには一辺何mのタイルで敷き詰めるのがよいか。

(解答) 最大公約数の問題だから、それぞれ素因数分解して

$28＝2^ 2\times7$ $\ \ \ \$ $95=5\times19$ よって最大公約数は1 （つまり28と95は互いに素）

　　　これを実際のタイル職人は、計算せずに正方形の１辺を探り当てます。　

　　　どうするのでしょう？

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 横95

縦28

$\require{color}\textcolor{blue}{まず短い辺28の正方形を取れるだけとり（３つ分とれます）}$

$\require{color}\textcolor{blue}{余った部分から短い辺11の正方形を取れるだけとり（２つ分とれます）}$

$\require{color}\textcolor{blue}{余った部分から短い辺6の正方形を取れるだけとり（１つ分とれます）}$

$\require{color}\textcolor{blue}{余った部分から短い辺5の正方形を取れるだけとり（１つ分とれます）}$

$\require{color}\textcolor{blue}{余った部分は短い辺1の正方形で敷き詰められる}$

ご存じの方も多いと思いますが、これが互除法です。

これを式で書くと

$95=28\times3+11$ ・・・・＊

$28=11\times2+6$

$11=6\times1+5$

$6=5\times1+1$ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
さてここからが本題

問題 $\ \ \ \$ $28x+95y=3$ $\ \ \ \$ を満たす整数解をすべて求めよ。

方程式の問題は「未知数の個数＝式の数」が通例ですが、整数解を求める方程式は「未知数が２つなのに与えられた式は１つ」でも解けます。

ヒント) $\ \$ まず $28x+95y=1$ を解くことにします。これを満たす整数 $x\$ と $y\$ が１つでも求められれば解決しますが、あてもなく探すのは難しい。互除法の計算式（前述の＊以下の式）を利用して、１＝28〇＋95△の形に表すことを考えます。以下次回で。

otonaもドキdoki