整数について、もっと詳しく調べてみよう。
【第1章】
(1)除法の原理
Aを整数とし、Bを自然数とする。
A=Bq+r (0≦r＜b)
を満たす(q,r)がただ一つ存在する。
(例)14=5×2+4
-23=5×(-5)+2
(2)ユークリッドの互除法
A,Bは自然数で、A＞Bとする。
A=Bq+r (0≦r＜B)のとき、
AとBの最大公約数とBとrの最大公約数は等しい。
(∵)AとBの最大公約数をG、Bとrの最大公約数をKとする。
A=Ga, B=Gbとする。
r=A-Bq=Ga-Gbq=G(a-bq)
GはBとrの公約数だから、G≦K
B=Ks, r=Ktとする。
A=Bq+r=Ksq+Kt=K(sq+t)
KはAとBの公約数だから、K≦G
よって、G=K
(例)A=1079, B=1577の最大公約数を求めよ。
(解)1577=1079+498
1079=498×2+83
498=83×6
aとbの最大公約数を、[a,b]と表す。
[1577,1079]=[1079,498]=[498,83]=83
【ユークリッドの互除法の活用】
(1)約分
1577/1079=(83×19)/(83×13)=19/13
(2)通分
1/1577+1/1079
=1/(83×19)+1/(83×13)
=13/(83×19×13)+19/(83×19×13)
=32/(83×19×13)
