ユークリッドの互除法［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 個の正の整数 f₁ , f₂ , … , f_n-1 , r₁ , r₂ , … , r_n が次の関係をみたしているとする。
　　p = r₁
　　q = r₂
　　r₁ = f₁ r₂ + r₃, ( r₃ > r₂ )
　　r₂ = f₂ r₃ + r₄, ( r₄ > r₃ )
　　　　︙
　　r_n-2 = f_n-2 r_n-1 + r_n, ( r_n > r_n-1 )
　　r_n-1 = f_n-1 r_n
　このとき、 gcd ( p , q ) = gcd ( r_j , r_j+1 ) ( j = 1 , 2 , … , n – 1 ) が成り立つことを j に関する数学的帰納法で示しなさい。
(3)　 p と q を互いに素な正の整数とする。このとき、 ap + bq = 1 を満たす整数 a , b が存在することを示しなさい。