Question

自称進の底辺

全くわかりません
どなたか教えていただきたいです！

338 第9章 整数の性質
応用問題 1
正の整数a,bに対して, a を bで割った商をα余りを とする.つ
まり、
a=bq+r
が成り立つとする.このとき,以下が成り立つことを示せ.
(1) aとbの公約数をd とすると,dはbとrの公約数でもある.
brの公約数をd' とすると, d' はaとbの公約数でもある.
(2)
(3) αともの最大公約数とbrの最大公約数は一致する.
精講
ユークリッドの互除法の 「核」 となる p336 の (*) を証明してみま
しょう. 考え方としては, 「αと6の公約数」と「brの公約数」
が (集合として) 一致することを示そうというものです. それがいえれば当然,
それぞれの最大公約数も等しいといえます.
解答
(1) αと6の公約数がdであるから,
a=dA, b=dB (A, B は整数)
とおける.このとき
d
bx 4
(es) bog=
bog=
(01)bog
r=a-bg=dA-dBg=d(A-Bg) dx (整数)
なので,rはdの倍数である. (bもdの倍数でもあるので,) dは6とrの公
約数である.
(2)との公約数がd' であるから,
WAON (ROSS)
b=d'B',r=d'R (B', R は整数)
とおける.このとき
a=bg+r=d'B'g+d'R=d' (B'q+R) d'x (整数)
なので, a は d' の倍数である. (bもd' の倍数でもあるので,) d' はαと
の公約数である。
(3)(1)(2)より「α と6の公約数」は「bとの公約数」 と(集合として) 一
致する.したがって, それぞれの最大公約数も等しくなるので、題意は示せ
た。
おません
る
持
る

ユークリッドの互除法