ユークリッドの互除法[2018 首都大学東京・理・数理科]

 以下の問いに答えなさい。
(1) 正の整数 p , q , f および整数 r が次の関係をみたしているとする。
  p = fq + r
 ただし、 0 ≦ r < q とする。このとき整数 d が p と q の公約数であることと、 d が q と r の公約数であることは同値であることを示しなさい。
(2) 正の整数 k , m の最大公約数を gcd ( k , m ) で表す。 p , q を p > q をみたす正の整数とする。また n ≧ 2 とし、2n – 1 個の正の整数 f1 , f2 , … , fn-1 , r1 , r2 , … , rn が次の関係をみたしているとする。
  p = r1
  q = r2
  r1 = f1 r2 + r3, ( r3 > r2 )
  r2 = f2 r3 + r4, ( r4 > r3 )
    ︙
  rn-2 = fn-2 rn-1 + rn, ( rn > rn-1 )
  rn-1 = fn-1 rn
 このとき、 gcd ( p , q ) = gcd ( rj , rj+1 ) ( j = 1 , 2 , … , n – 1 ) が成り立つことを j に関する数学的帰納法で示しなさい。
(3)  p と q を互いに素な正の整数とする。このとき、 ap + bq = 1 を満たす整数 a , b が存在することを示しなさい。

[2018 首都大学東京・理・数理科]

イズミの解答への道

解答

解説

シェアする

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

フォローする