otonaもドキdoki

大人も大人未満の人もドキドキすることを綴ります

数学一人旅３　　続・整数方程式

互除法から得られた＊の式を　余りを基準に書き直すと

$11=95-28\times3$ 　・・・・④

$6=28-11\times2$ 　　・・・・③

$5=11-6\times1$ 　　・・・・②

$1=6-5\times1$ ・・・・①　　　　　

最後の式①に順次上の式を代入していくと

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 　↓②　 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 　↓③

$1=6-(11-6\times1)\times1=6\times2-11=(28-11\times2)\times2-11$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 　↓④

$=28\times2-11\times5=28\times2-(95-28\times3)\times5=28\times17-95\times5$

これで $\ \$ $28\times17+95\times(-5)=1$ $\ \$ であることが判明 →３倍して

$28\times51＋95\times(-15)=3$ $\ \$ ということになります。

$28x＋95y=3$ $\ \ \ \$ を満たす全ての整数解は

技巧的ですが、辺々引くと

$28(51-x)+95(-15-y)=0$ となり　　←右辺０とするのがミソ

$28(51-x)=95(15+y)$ として

２８と９５が互いに素であるので　 $51-x=95k$ （ｋは任意の整数）となり

$x=51-95k$ を代入して　 $y=28k-15$ 　を得ます。

よって　答えは $x=51-95k$ $\ \$ , $\ \$ $y=28k-15$ $\$ (ｋは任意の整数）　

$\ \$

28と95は互いに素で、しかも比較的大きな数ですから $\ \$ $28x+95y=3$ $\ \ \ \$ を満たす整数解は、１つでも思いつきで見つけることは難しいですね。

28と95の代わりにもっと大きな素数を使えばどうでしょう。人間が自力で解くなら、互除法を利用しないとまず不可能です。ということは暗号に使えそうですね。