Pythonに手を出してみる③

見習い魔法使い、すなわち駆け出しプログラマとして数学の問題でも解いてみるか……と教科書を探したが、どこ？？？あ、しまいこんでた！というくらい数学と疎遠にしてきた。引っ張り出してきた数Aの教科書と、恐る恐る向き合ってみたい。

ユークリッドの互除法

a=133
b=161

while(a>0 and b>0):
   if(a>b):
       a=a%b
   else:
       b=b%a

   print(a,'と',b,'の最大公約数を求めよう')
   
if(a>b):
   print('答え：',a)
else:
   print('答え',b)

133 と 28 の最大公約数を求めよう
21 と 28 の最大公約数を求めよう
21 と 7 の最大公約数を求めよう
0 と 7 の最大公約数を求めよう
答え 7

いかにもアルゴリズムっぽい、ユークリッドの互除法に挑戦した（イマドキの大学入試に出そう）。多分いろいろと穴があるとは思うが、とりあえず133と161のときには使えた。

一次不定方程式

数Aの教科書ではユークリッドの互除法から一次不定方程式に繋げているが、自分はそんな綺麗に一次不定方程式を解いていなかった。いろいろと試して、当たるのを待った。そこで、ここでは互除法は「互いに素 or not」の判定に留めておき、方程式を腕ずく（Pythonずく？）で解けないか試してみる。

しかし、後日になりそうではある。

a0=133
b0=221
a=a0
b=b0
while(a>0 and b>0):
   if(a>b):
       a=a%b
   else:
       b=b%a
if(a>b):
   GCD=a
else:
   GCD=b
print(a0,'と',b0,'の最大公約数：',GCD)
if(GCD==1):
   print(a0,'x +',b0,'y = 1 を解いてみよう')
   print('ここに答えを書く')
else:
   print('互いに素じゃないから無理')

133と161を入れてみる。

133 と 161 の最大公約数： 7
互いに素じゃないから無理

133と221を入れてみる。

133 と 221 の最大公約数： 1
133 x + 221 y = 1 を解いてみよう
ここに答えを書く

腕ずく、かなり難しそうだが、自分も全くの当てずっぽうに解いていたわけではないので、挑戦するつもりだ。