�ҥ�Ȥ�����

�� ����� ruby �ǹ�����Ѥ��롣 require "matrix" �Ƚ񤯤��Ȥǹ��󤬻Ȥ���褦�ˤʤ롣

• �������ʬ��0���ܤ�0���ܡ��� 0 ��������Ϥ�롣
• �¤� $+$ , �Ѥ�(maxima�Ȥϰ�ä�) $*$ .

�� �桼����åɤθ߽�ˡ(���)

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

���Ф��ơ�$b$ �� $a$ �dz�ä����� $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)$ ����򤢤��衣