Euclidの互除法を書く - Ex 6.3 (d)(e)

おはようございます．

はじめての数論原著第4版

作者:Joseph H. Silverman
丸善出版

Amazon

『はじめての数論』の演習問題をやっていきます．

環境構築は終わっていますので，後はそんなに非自明な作業は残っていません．（間違える余地はありますが…）

問題 (d)

$b =0$ のとき，プログラムで何が起こるだろうか？その場合も適切に扱えるようプログラムを修正せよ．

入力が与えられた時点で，$b=0$ かどうかで分岐するプログラムを書けばいいかな．

こんな感じ．

# Euclidの互除法
## 入力
a = 2
b = 3
## 手続き
if b==0 and a==0:
    print(0,0,0)
elif b==0 and a!=0:  
    print(a,1,0)
else:
    ### aもbもゼロでない場合
    x = 1
    g = a 
    v = 0
    w = b 
    while w != 0:
        q = g // w
        t = g % w
        s = x - q*v 
        x = v
        v = s
        g = w
        w = t
    y = (g - a*x)//b
    print(g,x,y)

プログラムの本体を else の後に書かないといけないのが直感的にわかりづらいですね．

疑似コードだと

if $b=0$ then
Return ほげほげ
なんらかの操作

と書いてある場合は，$b = 0$ のときには「ほげほげ」部分が実行されて，アルゴリズムは停止します．（そうだったはず……）しかし，python では print したからと言ってアルゴリズムは止まらないので，アルゴリズム本体を else if 以下に続ける必要がありました．

この辺り，うまいことやる方法があるなら知りたいですが，ちょっと調べただけではわかりませんでした．今後の宿題ですね．

問題 (e)

以降の応用では $x > 0 $ を満たす解を求めることが有用となる．プログラムが常に $x>0$ の解を求めるよう修正せよ．

これもそんなに苦労しませんね．

# Euclidの互除法
## 入力
a = 2
b = 3
## 手続き
if b==0 and a==0:
    print(0,0,0)
elif b==0 and a!=0:  
    print(a,1,0)
else:
    ### aもbもゼロでない場合
    x = 1
    g = a 
    v = 0
    w = b 
    while w != 0:
        q = g // w
        t = g % w
        s = x - q*v 
        x = v
        v = s
        g = w
        w = t
    y = (g - a*x)//b
    ### x > 0であるような解を返すように細工をする
    if x < 0 and b>0:
        while x < 0:
            x = x + b
            y = y - a
    elif x < 0 and b<0:
        while x < 0:
            x = x - b
            y = y + a      
    else:
        pass  
    print(g,x,y)

$(x,y)$ を $(x - b, y + a)$ に置き換えて $x$ が正になる点を探すというだけのコードを書いています．pass というのは何もしないという意味のコードで，$x $ が初めから正なら何もしなくていいということを反映しています．

常に $x>0$ になるようにしようか迷いましたが，$a=b=0$ なら $x=y=0$ とした方が自然なので，そのようにプログラムを組んでいます．

ちょっと汚いコードになってしまった気がしますが，まあ素直にやっていけないことはないんじゃないかと思います．

感想

jupyter の扱いにも少し慣れてきました．

次は何をしようかな．

パンの木を植えて

主として数学の話をするブログ

Euclidの互除法を書く - Ex 6.3 (d)(e)

問題 (d)

問題 (e)

感想