解答 1 問題1
(1) a, bがいずれも3の倍数でないとする．aとbを3で割った商をq1, q2，余りをr1, r2とす る．r1, r2= 1, 2である．
a= 3q1+r1, b= 3q2+r2
このとき
ab= 3(3q1q2+q1r2+q2r1) +r1r2
r1r2= 1, 2, 4であるから，abは3の倍数ではない．abが3の倍数であるという仮定に矛盾 した．
よってaとbはともに3の倍数である．
(2) (1)からaかbが3の倍数である．aが3の倍数とする．a+bが3の倍数でaが3の倍数な ので，その差であるbも3の倍数である．
bが3の倍数であるときも同様であり，aとbはともに3の倍数であることが示された．
(3) a2+b2= (a+b)2−2abであるから，この数とa+bが3の倍数なら，2abが3の倍数であ る．2と3は互いに素なのでabが3の倍数となり，(1)からaとbはともに3の倍数である．
(0) mnはpの倍数なので，mnの素因数分解にpが現れる．mもnもpの倍数でなければ，積 mnの素因数分解にpは現れない．これは素真数分解の一意性（3節定理4）と矛盾する．よっ て，mまたはnはpの倍数である．
(1) abがpの倍数なのでaかbのいずれかがpの倍数である．aがpの倍数とし，a=pa′とお く．a+bがpの倍数なのでこれをpNとおく．このとき
b= (a+b)−a=pN−pa′
となりbはpの倍数である．bがpの倍数のときも同様にaがpの倍数となる．よってaと bはともにpの倍数である．
(2) a2+b2= (a+b)2−2abであるから，この数とa+bがpの倍数なら，2abがpの倍数であ る．pは奇素数なので2とは互いに素である．よってabがpの倍数となり，(1)からaとb はともにpの倍数である．
(3) a3+b3= (a+b)(a2−ab+b2)であるから，a+bかa2−ab+b2の少なくとも一方はpの 倍数である．
a+bがpの倍数のとき，a2+b2がpの倍数なので(2)によってaとbはともにpの倍数で ある．
a2−ab+b2がpの倍数のとき，a2+b2がpの倍数なので，abがpの倍数である．aがpの 倍数とするとa2+b2がpの倍数であることからb2がpの倍数である．pは素数なのでbが pの倍数である．はじめにbがpの倍数であるときも同様である．よってaとbはともにp の倍数であることが示された．
別解
a3+b3= (a+b)(a2+b2)−ab(a+b)
であるから，ab(a+b)がpの倍数になる．a+bがpの倍数なら（2）よりa, bがpの倍数．
abがpの倍数ならa2b2もpの倍数なので，（1）からa2とb2がpの倍数．pは素数なので，
aとbがpの倍数．
(4) aがpの倍数なら，an+bnがpの倍数であることからbnもpの倍数．pが素数でであるか ら，bもpの倍数である．逆の場合も同様．そこでaもbもpの倍数あるか，両方ともpの 倍数でないかのいずれかである．
aもbもpの倍数でないとする．n >= 2のとき，
an+1+bn+1= (a+b)(an+bn)−ab(an−1+bn−1)
であるから，このときan−1+bn−1がpの倍数になる．くりかえし用いることにより，a+b とa2+b2がともにpの倍数になる．このとき（2）からa, bがpの倍数になり，aもbもp の倍数でないという仮定と矛盾する．よってaもbもpの倍数あることが示された．
解答 2 問題2
(1) 余りは0<=r(n)<= 7にある．よって
0< a−r(a)<4 3r(b)<=
28 3 a−r(a)は8の倍数なのでa−r(a) = 8．この結果
8< 4
3r(b) ⇐⇒ 6< r(b) よってr(b) = 7
(2) 同様にb−r(b) = 8, r(ab) = 7．
これからb= 8 +r(b) = 15．またab= 8k+ 7とおけ，b= 15なのでab= 8a+ 7aである．あ わせて
8(k−a) = 7(a−1)
である．8と7は互いに素なのでa−1は8の倍数．よってr(a) = 1．これからa= 8 +r(a) = 9．
解答 3 問題3
(1) 二つの自然数kとk+ 1の最大公約数をdとし，
k=dk′, k+ 1 =dh とおく．ここにk′, hはそれぞれ適当な整数である．
これから
1 =dh−k=d(h−k′)
∴ d= 1 つまりkとk+ 1は互いに素である.
(2) もし2k+ 1とk+ 1に1より大きい公約数があれば，2k+ 1−(k+ 1) =kよりkもその公 約数を約数にもつ．kとk+ 1が互いに素であることと矛盾．よって2k+ 1とk+ 1も互い に素．
さらに2k+ 1とkの公約数は2k+ 1−2·k= 1より，1しかない．よって2k+ 1 =n2, k+ 1, k は互いに素である．
nがk+ 1やkと1より大きい公約数をもてば，n2がk+ 1やkと1より大きい公約数を もつ．
2k+1 =n2, k+1, kは互いに素なので，これはあり得ない．よって，三つの自然数n, k, k+1 は互いに素である.
(3) n2= 2k+ 1なので，
n2+k2= (k+ 1)2
より，3数n, k, k+ 1は直角三角形の3辺であり，(2)から互いに素である．
これは任意の奇数nに対して成立する．奇数は無数にあるので，三つの互いに素な自然数を 三辺の長さとする直角三角形が無数にあることが示された．
注意 3 本問は，3数の最大公約数が1であるピタゴラス数の簡単な作り方を示している．
任意に奇数を選ぶ．n= 11としてみよう．
n2= 121 = 2·60 + 1 すると，(11, 60, 61)はピタゴラス数である．実際
112= 121, 602= 3600, 612= 3721 である．
しかし，これですべてのピタゴラス数が作れるわけではない．
解答 4 問題4 (1)
b(p2+q2) =apq · · ·⃝1
左辺はbの倍数．aとbが互いに素なのでpq はb の倍数である．
(2) pと qの最大公約数をg とし，
p=gp′, q=gq′, (p′とq′は互いに素) とおく．このとき⃝1 は
bg2(p′2+q′2) =ag2p′q′ となる．つまり
b(p′2+q′2) =ap′q′ · · ·⃝2
(1)と同様にp′q′ がb の倍数になる．p′q′ =bk とおく．このとき⃝2 から p′2+q′2=ak
ここでk̸= 1 なら
p′2+q′2とp′q′が互いに素でない
⇐⇒ p′2+q′2+ 2p′q′とp′q′が互いに素でない
⇐⇒ (p′+q′)2とp′q′が互いに素でない
⇐⇒ p′+q′とp′q′が互いに素でない
⇐⇒ p′かq′の少なくともいずれかとp′+q′が互いに素でない
⇐⇒ p′とq′が互いに素でない
ゆえにk= 1 となり，b=p′q′ ，a=p′2+q′2 ．つまり
√a+ 2b=p′+q′．
これは自然数である．
解答 5 問題5
(1) n+ 2とn2+ 1の公約数をdとおく．(n2+ 1)−(n+ 2)(n−2) = 5なので，左辺はdの倍数 である．右辺が5なのでdは5の約数．つまりd= 1, 5である．
(2) (1)よりn+ 2とn2+ 1が1以外に公約数をもてばそれれは5である．n+ 2が5の倍数と なれば，(1)の恒等式からn2+ 1も5の倍数となる．よってn+ 2が5の倍数となることが 必要十分条件である．条件を満たすすべてのnは次のものである．
n= 5k−2 (k= 1, 2, · · ·) (3) 恒等式
4(n2+ 1)−(2n+ 1)(2n−1) = 5
より2n+ 1とn2+ 1が1以外に公約数をもてばそれは5である．従って2n+ 1が5の倍数 であることが必要十分条件である．2n+ 1は奇数なので5と奇数の積のときにかぎりnが存 在する．
2n+ 1 = 5(2k−1) (k= 1, 2, · · ·) これから条件を満たすすべてのnは次のものである．
n= 5k−3 (k= 1, 2, · · ·) 解答 6 問題6
(1)
a1= 1998, b1= 185 1998 = 185×10 + 148より a2= 185, b2= 148 185 = 148×1 + 37より a3= 148, b3= 37 148 = 37×4 + 0より a4= 37, b4= 0
a5= 37, b5= 0
(2) bn̸= 0 のときbn+1は an をbn で割った余りであるから余りの定義より，
0<=bn+1< bn
bn= 0のとき 数列{bn}の定義からbn+1=bn ．よって 任意のk, l, nについてbn >=bn+1
(等号はbn= 0のときに限る)が成立する．
(3) もしbn= 0となる nが存在しないとすると，すべてのbn は自然数でしかも bn> bn+1
が成り立つ．このことは 集合{bn | n= 1, 2, · · · }に最小値が存在しないことになり，自 然数の部分集合にはつねに最小値が存在するという，自然数の基本性質と矛盾する．よって bn= 0 となるnが存在する．
(4) (a, b)で aとbの最大公約数を表すことにする．bk ̸= 0のとき (ak, bk) = (bk, bk+1) を示す．
akをbkで割った商をqkとおくと，ak=bk·qk+bk+1 とかける． これからak とbk の公約 数はbk+1 の約数になり，bkとbk+1の公約数である．bkとbk+1の公約数で最大のものが最 大公約数(bk, bk+1)である．ゆえに(ak, bk)<= (bk, bk+1)．またbk と bk+1 の公約数はak の約数になる．同様に考え(ak, bk)>= (bk, bk+1)である．
∴ (ak, bk) = (bk, bk+1)
これをいいかえると(ak, ak+1) = (ak+1, ak+2)．(3)からある自然数N でbN−1̸= 0, bN = 0 となるものがある．このとき
(k, l) = (a1, a2) =· · ·= (aN−1, aN) = (aN, bN) =aN N <=nの nで同様の等式が成り立つので題意が示された．