［定理 2.40］任意のa, b,c∈Z+に対して,次の3つの条件が成り立つ.
(i) a|a.
(ii) a|bかつb|aならば,a=b.
(iii) a|bかつb|cならば,a|c.
［証明］(i) a=a·1より明らか.
(ii) a|bのとき,あるq∈Z+が存在してb=aqとなる. q≥1より, a≤a+a(q−1) =aq=b.
同様にしてb≤aもいえる. したがって,a≤bとb≤aとがともに成り立つから,a=b.
(iii) a|bのとき,あるq∈Z+が存在してb=aqとなる. 同様に,b|cのとき,あるq0∈Z+が 存在してc=bq0となる. よって,
c=bq0 =aqq0. qq0∈Zであるから,c|a.
［注意 2.2］上の定理の(i), (iii)は,その前の定理を適用することで,負の整数にも拡張できる. し かし, (ii)は負の整数までは拡張できない. 例えば,−1 = 1·(−1), 1 = (−1)·(−1)より(−1)|1か つ1|(−1)であるが−16= 1である.
［定理 2.41］任意のa, b,c∈Zに対して,次のことが成り立つ.
(i) gcd(a, b) = gcd(b, a).
(ii) gcd(a, b, c) = gcd(gcd(a, b), c).
［証明］(i) xを整数とする. 明らかに,xがaとbの公約数であることと,bとaの公約数である こととは同値である7). これより,aとbの任意の公約数がdの約数であることと,bとaの任意の 公約数がdの約数であることとが同値であることも明らかである8).
(ii) d= gcd(a, b, c),d0 = gcd(gcd(a, b), c),d00= gcd(a, b)とおく.
d|a, d|bよりd|d00. また, d|c. ゆえにd|d0. 逆に,d0|d00であり,d00|aだからd0 |a. 同様 にd0 |b. 一方, d0 |cでもある. したがってd0 |d. ゆえに, d0 |dかつd|d0より, d=d0. ここで, d >0,d0 >0であることに注意せよ.
m∈Zに対して,mの倍数全体からなる集合をmZとおく. すなわち mZ={mx|x∈Z}
とする.
［定理 2.42］a,b∈Zとし,
I={ax+by|x, y∈Z}
とおく. このとき,あるd∈Zが存在して
I=dZ, d= gcd(a, b) が成り立つ.
［証明］S={x∈N|x∈I, x6= 0}とおく. Nの整列性により,Sの最小元d >0が存在する. こ のとき,あるx,y∈Zが存在して
d=ax+by と書ける.
I=dZを示せばよいが, dZ⊆Iは明らかなので9),I⊆dZを示せば十分である.
z∈Iとする. あるq, r∈Zが存在して
z=dq+r, 0≤r < d
7)二つの命題P,Qについて,「PかつQ」と「QかつP」とが同値であることに注意して,Pとしてx|aをとり,Q としてx|bをとればよい.
8)きちんと証明すれば,aとbの公約数全体の集合をAとし,bとaの公約数全体の集合をBとし,dの約数全体の集 合をDとするとき,xがaとbの公約数であることと,bとaの公約数であることとが同値であるからA=B. よって A⊆D⇔B⊆D.
9)任意のz∈Zに対してdz= (ax+by)z=a(xz) +b(xz)∈Iとなるから.
となる. 適当なu,v∈Zをとって
z=ax+by と書けば,
r=z−dq=a(u−xq) +b(v−yq)∈I.
ところが,dの最小性によりr= 0でなければならない. よってz=dq∈dZ. ゆえにI⊆dZ. a=a·1 +b·0,b=a·0 +b·1よりa, b∈I=dZ. よってdはa,bの公約数である. また,a,b の任意の公約数wに対して
w|(ax+by) =d.
ゆえにdはa, bの最大公約数である.
［定理 2.43］a,b,c∈Zとし, a, bの最大公約数をdをする. このとき,次の2つの条件は同値で ある.
(i) あるx,y∈Zが存在してax+by=c.
(ii) d|c.
［証明］Iを前定理の通りとすると, (i)⇔c∈I⇔c∈dZ⇔(ii).
a,bを整数とする. gcd(a, b) = 1が成り立つとき,aとbとは互いに素であるという.
［定理 2.44］a,b∈Z, m∈Z+とする. このとき
gcd(ma, mb) =m·gcd(a, b) が成り立つ.
［証明］d= gcd(a, b),d0 = gcd(ma, mb)とおく.
適当なx,y∈Zをとって
d=ax+by と書き,両辺にmを掛けると,
md= (ma)x+ (mb)y.
ゆえにd0|md.
逆に 適当なx0,y0∈Zをとって
d0= (ma)x0+ (mb)y0 と書けば,
d0 =m(ax0+by0).
d|a,d|bよりd|ax0+by0であるから,md|d0. したがってd0=md.
［定理 2.45］a,b,c∈Zとし, gcd(a, b) = 1とする. このとき,a|bcならばa|c.
［証明］gcd(a, b) = 1より,あるx,y∈Zが存在して ax+by= 1.
両辺にcを掛ければ,
acx+bcy=c.
a|bcであるから,この左辺はaの倍数である. ゆえにa|c.
［定理 2.46］a,b,c∈Zとする. このとき
gcd(a, b) = gcd(a, c) = 1⇐⇒gcd(a, bc) = 1.
［証明］まず, gcd(a, b) = gcd(a, c) = 1を仮定してgcd(a, bc) = 1を証明する. d = gcd(a, bc) とおくと, d| a, d | bc. もし仮にgcd(d, b)> 1ならば, d |aよりgcd(a, b)> 1となる. これは gcd(a, b) = 1に反する. よってgcd(d, b) = 1. したがって前の定理よりd|c. ところが,d|aより dはa,cの公約数である. 仮定よりgcd(a, c) = 1であったから,d= 1でなければならない.
次に, gcd(a, b)>1ならばgcd(a, bc)>1となることは明らかである10). 同様に, gcd(a, c)>1 ならばgcd(a, bc)>1となることも明らかである. よって,
gcd(a, b)>1またはgcd(a, c)>1 =⇒gcd(a, bc)>1.
対偶をとれば
gcd(a, bc) = 1 =⇒gcd(a, b) = gcd(a, c) = 1 となる.
整数a,b∈Zに対して,aとbの両方の倍数であるような整数のことをaとbの公倍数という.
l∈Zがaとbの最小公倍数であるとは,次の3つの条件が成り立つときにいう.
• lはaとbの公倍数である.
• aとbの任意の公倍数はlの倍数になる.
• l >0.
aとbの最小公倍数を記号lcm(a, b)で表す.
3つ以上の整数に対しても,同様にして公倍数,最小公倍数を定義することができる. 例えばa,b, c∈Zに対して,a,b,cのそれぞれの倍数であるような整数をa,b,cの公倍数という. また, l∈Z がa,b,cの最小公倍数であるとは,次の3つの条件が成り立つときにいう.
10)d= gcd(a, b),d0= gcd(a, bc)とおく.d|bならばd|bc.よってd|d0である.d >0,d0>0だから,d≤d0.
• lはa,b,cの公倍数である.
• a,b,cの任意の公倍数はlの倍数になる.
• l >0.
a,b,cの最小公倍数を記号lcm(a, b, c)で表す.
［定理 2.47］任意のa, b,c∈Zに対して,次のことが成り立つ.
(i) lcm(a, b) = lcm(b, a).
(ii) lcm(a, b, c) = lcm(lcm(a, b), c).
［証明］(i) xを整数とする. 明らかに,xがaとbの公倍数であることと,bとaの公倍数である こととは同値である. これより,aとbの任意の公倍数がlの倍数であることと,bとaの任意の公 倍数がlの倍数であることとが同値であることも明らかである.
(ii) l= lcm(a, b, c),l0 = lcm(lcm(a, b), c),l00= lcm(a, b)とおく.
a|l,b |lよりl00 |l. また, c| l. ゆえにl0 |l. 逆に, l00| l0であり, a| l00だからa|l0. 同様に b |l0. 一方,c |l0でもある. したがってl|l0. ゆえに, l|l0かつl0 |lより, l =l0. ここで,l >0, l0 >0であることに注意せよ.
［定理 2.48］a,b∈Z+の最大公約数をd,最小公倍数をlとする. このとき ab=dl
が成り立つ.
［証明］a=a0d,b=b0dとおく.
d= gcd(a, b) = gcd(a0d, b0d) =d·gcd(a0, b0).
d >0なのでgcd(a0, b0) = 1. 一方,lはaの倍数であるから,あるk∈Z+が存在して l=ak=a0kd.
lはbの倍数でもあるから, b|a0kdである. b=b0dよりb0d|a0kdであり,d6= 0よりb0 |a0kが得 られる. gcd(a0, b0) = 1であるから,b0 |kである. したがって,あるt∈Z+が存在してk=b0t. こ のとき,
l=ak=ab0t=a0db0t=a0bt.
ゆえに,
l
t =ab0=ba0.
したがってl/tはa,bの公倍数である. lが最小公倍数であることからlはl/tの約数,よってl≤l/t.
したがってt= 1でなければならない11).ゆえにab=ldが得られる.
11)l >0,t >0のとき,l/t < l⇔l < l t⇔l(t−1)>0⇔t−1>0⇔t >1.