04-02ユークリッド互除法と一次不定式で理解しておきたいこと

ユークリッド互除法と一次不定式で特に理解しておきたいところでは、最大公約数の求め方、
一次不定式の解き方を理解して身につける必要があります。

1.ユークリッド互除法を使った最大公約数の求め方
  比較的小さい数の最大公約数は素因数分解で解けるが、大きい数字の場合
  ユークリッド互除法が有効なので、やり方を覚えておきましょう。
  $a$と$b$の最大公約数は、$a$を$b$で割ったあまり$r$と$b$の最大公約数になる性質を使っています。
  いろいろなやり方が割り算の筆算のやり方が覚えやすいです。
  
  
2.一次不定式の解き方
  「$ax+by=c$となる整数$x、y$の組を求めよ」という問題を一次不定式を解く問題といいます。
  変数が$2$個の一次式を解くためには、$2$つの式が必要なのですが、
  この問題では式が$1$つのため、解がたくさんあります。
  
  ①小さい数字の場合
   代表解を順番に探し、その後、倍数の関係に変形して一般解を求めます。
  (例)$7x+5y=23$であれば
   係数の小さい数までを係数の大きい変数に入れて順番に探すと見つかります。
   $5y=23-7x$として、$x=0~4$を試す。
    $5y=23-7\times0=23$
    $5y=23-7\times1=16$
    $5y=23-7\times2=9$
    $5y=23-7\times3=4$
    $5y=23-7\times4=-5$
   つまり、代表解は$x=4、y=-1$
    $7(x-4)+5(y+1)=0$
    $7(x-4)=-5(y+1)$
    $7$と$5$は互いに素であるため、$x-4=5k、y+1=7k(kは整数)$である。
   すなわち
   $x=5k+4、y=7k-1$
   
  ②$(ax+by=1)$で、$a、b$大きい数字の場合
   解き方は、ユークリッド互除法を利用して解きます。
  (例)$37x-90y=1$であれば
   互除法により
    $a=90、b=37$とおくと
    $90=37\times2+16$ から $16=a-2b$
    $37=16\times2+5$ から $5=b-2(a-2b)=-2a+5b$
    $16=5\times3+1$ から $1=a-2b-3(-2a+5b)=7a-17b$
   つまり、$37\cdot(-17)-90\cdot(-7)=1$
    $37(x+17)-90(y+7)=0$
    $37(x+17)=90(y+7)$
    $37$と$90$は互いに素であるため、$x+17=90k$、$y+7=37k(kは整数)$である
   すなわち、
    $x=90k-17、y=37k-7(kは整数)$
  
  ③$(ax+by=c)$で、$a、b$大きい数字の場合
   解き方は、②の解を$c$倍して解きます。
  (例)$37x-90y=4$であれば
   まず、$37x-90y=1$の代表解を求めます。
   ②の互除法より
    $37\cdot(-17)-90\cdot(-7)=1$
   これを、両辺4倍にして
    $37\cdot(-17\times4)-90\cdot(-7\times4)=4$
    $37\cdot(-68)-90\cdot(-28)=4$
    $37(x+68)-90(y+28)=0$
    $37(x+68)=90(y+28)$
    $37$と$90$は互いに素であるため、$x+68=90k$、$y+28=37k(kは整数)$である
   すなわち、
    $x=90k-68、y=37k-28(kは整数)$
  
  ④その他、合同式を使った解き方があります。
   ただ、うまく計算が少なくなるように問題が作られていないと、
   最後の計算が大変なので、博打的要素があります。
   逆に言えば、②や③と比べてかなり楽に解ける可能性もあるということです。
  (例)$37x-90y=4$であれば
    係数の小さい方を法とします
    $37x-90y≡4(\bmod 37)$
    $-90y≡4(\bmod 37)$      $37x≡0(\bmod 37)$のため
    $(-37\cdot 3+21)y≡4(\bmod 37)$
    $21y≡4(\bmod 37)$     $-37\cdot 3y≡0(\bmod 37)$のため
     $y=9$  ←ここが$y=0~36$を計算しないといけないため大変
    $37x-90\times9=4$より
     $x=22$
    $37(x-22)-90(y-9)=0$
    $37(x-22)=90(y-9)$
    $37$と$90$は互いに素であるため、$x-22=90k$、$y-9=37k(kは整数)$である
   すなわち、
    $x=90k+22、y=37k+9(kは整数)$
   ③と答えが違うように見えるが、$k$に$k-1$を入れれば同じになります。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする