ヒントと問題

◎ 今回は ruby で行列を用いる。 require "matrix" と書くことで行列が使えるようになる。

• 行列の成分は0行目や0列目、と 0 から数え始める。
• 和は $+$ , 積は(maximaとは違って) $*$ .

◎ ユークリッドの互除法(初級)

$$v_0= \begin{pmatrix} a \\ b \end{pmatrix}$$

に対して、$b$ を $a$ で割った商を $q$ , 余りを $r$ とおく。

$$A(q)= \begin{pmatrix} -q & 1 \\ 1 & 0 \end{pmatrix}$$

とおくと、

$$v_1=A(q)v_0= \begin{pmatrix} r \\ a \end{pmatrix}$$

$v_1$ に対して同様な操作を行なう。これを繰り返すことにより、 ベクトル $v_0,v_1,\dots,$ を得る。これが互除法の操作と一致することを確かめよ。

○ ruby による $A(q)$ の実装例(ruby では大文字小文字を 区別する。ここでは小文字の変数や関数しか扱わないことにする 。)

def amatrix(q)
  return(Matrix[[-q,1],[1,0]])
end

◎ 拡張されたユークリッドの互除法

$$v_0= \begin{pmatrix} a \\ b \end{pmatrix}$$

から出発して、$A(q)$ の形の行列をどんどん掛けることで、 最終的に

$$\begin{pmatrix} 0 \\ d \end{pmatrix}$$

の形のベクトルを得るのが前の問題の趣旨であった。

今度は $v_0$ の他にもうひとつ単位行列 $E$ をならべる。

$$B_0=(v_0 \vert E) = \begin{pmatrix} a \vert & 1 & 0 \\ b \vert & 0 & 1 \end{pmatrix}$$

$a,b$ に $A(q)$ の形の行列を掛ける際に、後ろの行列にも同じ行列を 掛ける。

これを何度か繰り返せば、

$$\begin{pmatrix} 0 \vert & p & q \\ d \vert & r & s \end{pmatrix}$$

という行列を得る。これをうまく利用せよ。

## $B%W%m%0%i%`Nc(B
require "matrix"
def amatrix(q)
  return(Matrix[[-q,1],[1,0]])
end

def gojoho(a,b)
  v=Vector[a,b]
  m=Matrix.I(2)            ###m$B$N=i4|CM$OC10L9TNs(B
  while (true)             ###$BL58B%k!<%W(B
    if (v[0]==0) then      ### == $B$KCm0U!#(B
      return([v[1],m])     ### v[0]=0 $B$J$iC&=P(B 
    end
    q1=v[1].div(v[0])
    m1=amatrix(q1)
    v=m1*v
    m=m1*m
  end
end

### $B<B9TNc(B
p gojoho(113,25)

最終問題: $a=10^8-1$ と $b=30^7$ とおくとき、$m,n$ の最大公約数 $d$ と、 $ax+by=d$ を満たす整数の組 $(x,y)$ の例をあげよ。