小さな体を作ろう

up:: 代数学

Swiftで代数学入門 〜 5. 小さな「体」を作ろう - Qiita

もう言ってしまうが、Z_<n>で体を取るのはnが素数の時。
けどそれが正しいかどうかを判定するため、ユークリッド互除法とベズーの等式を使う。

ユークリッド互除法は二つの数の最大公約数を求めるためのアルゴリズム。
一方の数でもう一方を割り、出てきた余りでそのもう一方を再度割り……を繰り返すと、余り0になった時の除数が最大公約数になる。

表記はgcd。これに二つの値を入れ、$\gcd (1732,194)$という風に表示する。
なおgcdはGreatest Common Divisor、つまり最大公約数の略。計算はこう。

gcd(a,b), a=x・b+y, ←b2y1, b=0→a

swiftでは余り計算して入れればいいのでもっと楽。
上の計算では余り0でやめるが、プログラムでは除数0まで続けることに注意。

func gcd(a: Z, _ b: Z) -> Z {
    switch b {
    case 0:
        return a
    default:
        return gcd(b, a % b)
    }
}

ちなみに$\gcd (1732,194)=\gcd (194,1732)$と交換則が成り立つ。
プログラム上でもこれは表現されている。

続いてベズーの等式。
左右に a歩、b歩 進むのを何回か繰り返してれば、いずれスタート地点から右に d=gcd(a,b) 歩進んだところに辿り着ける。
真面目に言うと、$0$ でない整数 $a,b$ に対し、$ax+by=\gcd (a,b)$ となる整数 $x,y$ が存在する。

この式に従い、$\gcd (1732,194)$を変形して$\gcd (1732,194)=1732x+194y=2$にする。
このzとyは、ユークリッド互除法を下から解き直して代入していくと定まる。
a=x・b+y → y=a-x・b

諸々計算していくと、$(x,y)=(-14,125)$になる。

さてこのままだと実装できないので、ユークリッド側から漸化式にする。
初項に当たるgcdの中の数をそれぞれgcd(a0,b0)とする。
被除数an、除数bn、n回目の割り算の商をqn、余りをrnとする。

次はbnをrnで割る。
と書いてはいるが、とりあえずn+1の時のaとbを作る。

あとはbn=0の時のanを求めれば、gcd(a0,b0)を出せる。
ここで漸化式を行列とベクトルの積にして、計算を楽にする。

この変換が出来るかどうかは、知識と発想勝負。
あとはbn=0になった時、anがgcd(a0,b0)であることから再変換。bn+1を0と置き、anとbnがa0b0になるまで変換を繰り返して(下がって)いく。