整数の基本
整数の分野は高校の数学のなかでたいへん重要な分野である．数学の基礎であり，さまざまの論 証の基礎であり，また長い歴史をもつ．これまで高校の教科書に「整数」という単元はおかれてい なかった．ようやく 2012 年先行開始で数学 A に「整数の性質」がおかれ，基本的なことがらを習 うことになった．また高校の参考書では「整数」などの節を設けているものが多いが，問題の解法 という観点で書かれている．そのため，何が基本事項なのか，また何を根拠に示せばよいのかがた いへんわかりにくい． そこで，高校整数論の骨子となる部分を，基本事項には証明もつけてまとめた．いろいろ考えな がら読んでいくことができれば，それが力になる．整数問題において立ちかえるべき根拠となるこ とがらをまとめた．基本事項をしっかりおさえたうえで，自由に考えることが整数問題ではとくに 大切である． 高校範囲の整数問題には他にも，平方数の剰余，ペル方程式，格子点への応用など，まだまだ多 くの分野がある．しかしそれらは，本書の基本のうえに，問題演習として取り組めばよい．一方， 本書で取りあげた分野については，関連する大学入試問題を演習問題として紹介した．解答はそれ だけで完結するようにした．内容的なつながりをよく考えながら解いてみてほしい． 以下では自然数，整数，有理数，実数, 複素数の集合をそれぞれN, Z, Q, R, C と書く．定理の 証明やいくつかの注意および解答は小さい文字にした． 第 1 版，2009 年 9 月．第 2 版，2011 年 2 月．第 3 版，2012 年 9 月．目 次
1 自然数 2 2 整数の約数と倍数 5 3 素数 11 4 一次不定方程式 16 5 余りによる類別 22 6 フェルマの小定理 25 7 整式の整数論 29 8 解答 321
自然数
1.1
自然数とは
自然数は，人が成長する過程で最初に習得する数である．「いち，に，さん」とみかんを数えなが ら，みかんが 3 個あるということを覚える．このようにしてすでにある自然数を習うのだが，はじ めからこのように自然数ができあがっていたわけではない． ホメロスの『オデュッセイア』のなかに，羊を数える話がのっている．洞窟の入り口で羊が 1 頭 出てくるたびに小石を 1 個袋に入れる．羊飼いはその袋をもち歩く．夕方羊が 1 頭帰るたびに，そ の石を 1 個袋から出す．最後の羊が帰ったとき最後の小石が袋から出されれば，迷子の羊がいない ことがわかる． 皿にみかんを 1 個ずつ乗せてゆく．みかんが余るときもあれば，皿が余るときもある．そのなか でちょうど皿に 1 個ずつみかんが乗るときがある．このとき，皿とみかんの「何かが同じ」だと， 気づく．いったい何が同じなのだろう? と考えた人もいるかも知れない．皿とみかんが一対一に 対応する．朝の羊と小石を一対一に対応させておき，その小石と夕方帰ってきた羊とが一対一に対 応すれば，朝の羊と夕方の羊の増減はない．そこで何かが同じだ．一対一対応がつかないときは 違う． 「一体何が同じで何が違うのか」と考え，同じ「何」としての「数」という概念が育っていった． いつか，小石の代わりに「いち，に，さん，…」と数の言葉を用意しておけばよいことに人はどう して気づいたのだろう．あるいは実がなるまでに月の満ち欠けがどれだけくりかえされるか，こん なところにも数の言葉を発見した動機があるかも知れない． 数を表す言葉が生まれても，3 個のみかんは 3 個のみかん，皿 3 枚は皿 3 枚と 3 が抽象されな いまま用いられる膨大な時間があったにちがいない．そのときを経て，数 3 が抽象されていった． このように，個別のものの形や質などに規定された具体的な量から，個別の性質を捨て一般的な 「数」を抽象する力を，人間は長い時間をかけて身につけた． 人間が数をつかみ，それが親から子へと伝えられて，子供は成長のなかで数を身につける．大人 からの伝達の作用によって，人類の長い歴史が凝縮されて，子供のなかで反復されるのだ．みかん のように数えられるものの個数がつかまれたなら，つぎは「水がバケツに 3 杯ある」などのように 連続量をはかる単位が生まれ，単位の個数として水の量をつかむことができるようになったと考え られる． このようにして見いだされた自然数は，数えるという行為と一体である．数えるという行為と は，このものを認識し，その次のものを確認して，自然数によって指示される抽象的な数との間に 対応をつけていく，ということにある．最後に対応した数をその集合の要素の個数と認識する，と いうことである． このことを定式化して自然数を改めて数学の対象として定義しなおす． 定義 1 1 からはじめて,「1 たす」という操作だけで作られる数の集合を自然数の集合といい，そ の要素を自然数という． 数学ではこのように日頃当然わかったものとして使っている自然数を，改めて「自然数とは何 か」と考えなおして，言い直してみることが大切だ． 「たす」という操作を記号「＋」で表す．最初の対象「1」と操作「+」とその「くりかえし」， これだけである．1 に 1 たした 1+1 を 2 と記し，2 に 1 たした 2+1 を 3 と記し，以下順に名前と文字をつけてゆく．このように命名された要素の集合をN と記す．その各要素を自然数という．定義 の「だけで作られる」というところが大切である．つまり条件を満たすなかで最小の集合である．
1.2
自然数の基本性質
この定義から自然数の集合N は次のような性質をもつことが示される．これを証明するために は，自然数の定義をさらに厳密にしなければならない．それは略する．その意味を説明する． (i) 大小関係 2 つの自然数 a と b は，a から始まって 1 たす操作をくりかえすことで b になるとき a < b と定め，a は b より小さい，b は a より大きいという． 異なる自然数 a と b はつねに，いずれかが他方より大きく，比較がいつでもできる． (ii) 最小要素の存在 自然数の集合N の部分集合には最小の要素がただ一つ存在する． 要素が自然数からなる集合には最小の要素がただ一つ存在することを主張する．これは，整数分 野の諸問題で存在証明の根拠になる． 一方，整数からなる集合や有理数からなる集合では最小要素があるとはかぎらない．例えば {−5, −6, −7, · · ·} = {a | a は − 5 以下の整数 } { 1 2, 1 4, 1 8, · · · } = { 1 2k k は自然数 } などはいずれも最小の要素がない． 整数の部分集合でも，そのうち正の要素からなる部分集合には最小の要素が存在する．一次不定 方程式の解の存在の証明に，この最小要素の存在を用いるところがある． (iii) 数学的帰納法の原理 N の部分集合 A が条件： 1∈ A，かつ x ∈ A なら x + 1 ∈ A を満たすなら，A はN 自身である． これがなぜ数学的帰納法の原理なのか． すべての自然数 n であることが成り立つことを示すときに用いる数学的帰納法という証明方法 がある．n = 1 のときに成り立ち，n = k のときに成り立つと仮定すると n = k + 1 でも成り立つ． するとこれですべての自然数で成り立つと言える．有理数や実数ではこうはいかない．ということ は，この証明方法が可能な根拠は自然数の性質にあるということになる． それが (iii) 数学的帰納法の原理である．これはどういうことを言っているのか．このことの理 解は高校範囲を越えるのであるが，自然数の大切な性質なので書いておこう． p(n) を自然数 n を含む命題とする．数学的帰納法とは，すべての自然数 n で p(n) が真である ことを証明するための，次のような証明方法であった．(1) p(1) が真である． (2) p(k) が真なら p(k + 1) が真である． (3) (1), (2) より, すべての自然数 n に対して p(n) が真である． この証明方法ですべての自然数で成立することが，(iii) 数学的帰納法の原理から次のように示さ れる． 条件 p(n) が成立する自然数 n よりなるN の部分集合を A とする．つまり A ={n | n ∈ N, かつ p(n) が成立する．} とおく．数学的帰納法の (1) は 1∈ A，(2) は k ∈ A なら k + 1 ∈ A が成り立つことを示している． すると自然数の性質 (iii) より A =N．つまりすべての自然数 n に対して p(n) が成立する． (証明終わり) このように数学的帰納法は，自然数の性質を根拠とする証明法である． 自然数の演算 自然数の集合N の要素 a と b の和 a + b，積 ab は再び N に属する．また和と積に 関して a(x + y) = ax + ay が成り立つ．この公式を分配法則という．また，演算の結果がふたたびその集合に属することをそ の演算に関して閉じているという．自然数の集合はN は加法と乗法に関して閉じている．これに 対して減法と除法については閉じていない． N を含み加法・減法で閉じている最小の集合が整数の集合 Z であり，Z を含み乗法・除法で閉じ ている最小の集合が有理数の集合Q である．
2
整数の約数と倍数
2.1
整数の集合と除法
自然数を基礎にして，さらに 0 と負の数を加えて整数の集合ができる．整数の集合をZ とする． Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · ·} である．詳しくいうと，自然数 a に対して a + x = a となる x を 0 と表す．さらにこの 0 を用いて a + x = 0 となる x を−a と表す． 自然数に，このようにして得られる数をすべて加えて得られる集合が整数の集合Z である．0 に 自然数を加えて得られる整数を正の整数，0 から自然数を引いて得られる整数を負の整数，という． 正の整数と自然数は同じ意味になる．整数の集合Z は，加法，減法，乗法に関して閉じている． 除法の定理 整数の集合Z は，演算の除法 (割り算) に関しては閉じていない．整数では除法をお こなうとその結果が 12÷ 3 のように Z に属する場合と，12 ÷ 5 のように属さない場合がある．属 さない場合はZ の中では余りが出る． 割り算を行うとき，まずどのように考えるか思い起こそう．例えば 75 を 6 で割るとき，6 が何 回分 75 の中にあるかを考えるのではないか．そして，6 にその数を乗じた数を 75 から引く．それ が余りになる．次の定理と証明はそれを定式化したものである． 定理 1 a を整数，b を 0 でない正の整数とする．このとき， a = qb + r , 0 <= r < b となる整数 q, r がただ１組存在する．q を a を b で割った商，r を余りという． 証明 正の整数 b に対して，整数 a は次のような不等式のいずれか一つに入る． · · · , −3b <= n < −2b, −2b <= n < −b, −b <= n < 0, 0 <= n < b, b <= n < 2b, · · · いいかえると整数 a と正整数 b に対して，q は整数を動くとすると，qb は q に関して単調増加な ので qb <= a < (q + 1)b となる整数 q がただ一つ存在する． この q に対して r = a− qb とおく．qb <= a < (q + 1)b より 0 <= r < b であり a = qb + r が成り立つ．存在は示せた．一つしかないことを示す．このような q, r が二通りあったとし， a = q1b + r1, a = q2b + r2, 0 <= r1, r2< bとする．これから 0 = (q1− q2)b + r1− r2 よって，r1− r2は b の倍数である．ところが 0 <= r1, r2< b なので， −b < r1− r2< b この範囲の b の倍数は 0 しかない．よって r1− r2= 0．これから q1= q2となり，一通りしかない ことが示された． (証明終わり) このように整数の割り算では，整数のなかでの商と余りが一通りに定まる．整数の論証の基本は この除法に関する性質が根拠になる．除法は整数の論証の基礎である．論証のなかで除法を適切に 使えることが大切だ．
2.2
約数・倍数と最大公約数
約数・倍数の定義 除法の定理から約数や倍数の基本性質が導かれる． 定義 2 整数 a が b の倍数であるとは，a = bq となる整数 q が存在することと定める．このとき b は a の約数という. 除法の定理によって，a が b の倍数であることは，a を b で割った余りが 0 で あることと同値である． 6 の約数は 2 や 3 であるが，−2 や −3 も約数ではないのか．確かに 6 = (−2)(−3) も因数分解で あることには変わりない．このように，約数や倍数には±1 の自由さがあり，割り切れるとか，因 数分解とか，整除に関することはすべて，ある整数で成り立てばそれに−1 をかけても成り立つ． だから逆に割れる割れないなどは正の整数で考えればよいことになる． ±1 は逆数もまた整数である．逆数もまた整数であるものを単数という．Z の単数は 1 と −1 で ある． 最大公約数と最小公倍数 さらに，公約数，公倍数が定義される． 定義 3 二つ以上の整数 a, b, c, · · · に共通な倍数をそれらの整数の公倍数という．0 は任意の 整数の公倍数である．それを除けば公倍数の絶対値は a, b, c, · · · のいずれの絶対値よりも小さくはないので，公倍数の中に正で最小のものがある．それを最小公倍数 (least common multiple 略 して L.C.M.) という．
二つ以上の整数 a, b, c, · · · に共通な約数をそれらの整数の公約数という．1 は任意の整数の
公約数である．公約数の絶対値は a, b, c, · · · のいずれの絶対値よりも大きくはないので，公約数
の中に最大のものがある．それを最大公約数 (greatest common measure 略して G.C.M.，あるい は，greatest common divisor 略して G.C.D.) という．
最大公約数が 1 であるとき，その 2 数は互いに素であるという．また整数 a と b の最大公約数を 座標などと混同する恐れのないときは (a, b) と書く．(12, 32) = 4 のように用いる． 次の定理の証明においても除法の定理が基本定理として用いられる．日頃当然のように論証で 使っていることが除法の定理を基礎に厳密に示される．このことをおさえた上で高校数学の解答で 次定理は証明なしに用いてよい．証明は (1) のみおこなう．(2) 以下も同様に除法の定理をもとに 示されるので，一度試みてほしい．
定理 2 (1) 二つ以上の整数の公倍数は，最小公倍数の倍数である． (2) 二つ以上の整数の公約数は，最大公約数の約数である． (3) a, b の最小公倍数を l ，最大公約数を d とすれば ab = dl ． (4) a, b が互いに素で，整数 c と b との積 bc が a の倍数なら，c が a の倍数である． -(1) の証明 a, b, c, · · · の最小公倍数を l とし, m を任意の公倍数とする．m を l で割った商を q ，余りを r とすると m = ql + r, 0 <= r < l となる．l も m も a の倍数であるから l = al′, m = am′ とおくと r = m− ql = a(m′− ql′) より, r は a の倍数である．同様に b, c, · · · の倍数でもあり，r は a, b, c, · · · の公倍数となる． r が 0 でないとする．l より小さい正の公倍数 r があることになり, l が正で最小の公倍数である ことに矛盾する．よって r = 0．つまり m は l の倍数である． (証明終わり)
2.3
ユークリッドの互除法
24 と 42 の最大公約数を求めようとすれば，いずれをも割り切る素数を見い出して，順に割って いくのだ． 2) 24 42 3) 12 21 4 7 ∴ (24, 42) = 6 しかしこの方法には欠点がある．暗算で見つかるような小さい素数なら順次調べればよいが，6188 と 4709 のなかの素数のように少し大きいと，発見するのはなかなか難しい． ところが，つねに最大公約数を見い出すことのできる方法がある！ それがユークリッドの互除 法である．その根拠は次のような除法の式からの結論である． 定理 3 a > b > 0 を整数とし, a を b で割った余りを r とすると，(a, b) = (r, b) である． 証明 a を b で割った商を q とする．a = bq + r である． (a, b) = d1とすると a = a′d1, b = b′d1とおける. r = a′d1− b′d1q = d1(a′− b′q) これより r も d1で割れる. よって,d1 は b と r の公約数となり， d1<= (b, r) = d2． 次に (b, r) = d2 とすると, b = b′d2, r = r′d2 とおける. a = b′d2q + r′d2= d2(b′q + r′) より同様に d2<= (a, b) = d1．よって d1= d2 ，つまり (a, b) = (b, r) である． (証明終わり) ここで除法の定理により 0 <= r < b である．余りはもとの数より小さい．最大公約数をより小さ い数の間の最大公約数を求める問題に還元してゆくことができるのではないか．つまり，割り算を くりかえして最大公約数を追いつめることができる．これは大きな発見だった． 実際にやってみよう．例 1 (6188, 4709) を求めよう．順次割り算を行う． 6188 = 4709× 1 + 1479 4709 = 1479× 3 + 272 1479 = 272× 5 + 119 272 = 119× 2 + 34 119 = 34× 3 + 17 34 = 17× 2 これより最大公約数の次の系列を得る． (6188, 4709) = (4709, 1479) = (1479, 272) = (272, 119) = (119, 34) = (34, 17) = 17 こうして確かに最大公約数が求まる．この方法をユークリッドの互除法という． 「必ずできる一般的方法」をアルゴリズムという．ユークリッドの互除法はアルゴリズムの基本 例である．その他の有名なアルゴリズムは 2 次方程式の解法である．平方完成して移項して平行根 をとることにより解ける．この過程を一つにまとめたのが 2 次方程式の解の公式である． ユークリッド 「ユークリッド」は英語圏での書き方 (英語表記 Euclid) とその読み方で，本来は 「エウクレイデス」と発音する． エウクレイデス（Eukleides，紀元前 365 年?∼紀元前 275 年?）は古代ギリシアの数学者，天文 学者とされる人で，アテナイで学びプトレマイオス 1 世治下のアレクサンドリアで教えた．ちなみ にプトレマイオス 1 世とは，アレクサンドロス 3 世（アレキサンダー大王）の部下であったマケド ニア地方出身のギリシア人で，大王の死後，エジプトの支配を継ぎ，プトレマイオス朝を創始した． 『原論』はラテン語圏，アラビア語圏にもたらされ，その後各地で二千数百年にわたって幾何 学，いや数学そのもの基本となる書物であった．この書は 13 巻から成り，1∼6 巻は平面幾何，7 ∼9 巻は数論，10 巻は無理量，11∼13 巻は立体幾何を取り扱っている． 最大公約数を求める方法 であるユークリッドの互除法はこの『原論』にある．
2.4
演習問題
問題 1 解答 1 ［10 神戸文系 3 番］ a, b を自然数とする．以下の問に答えよ． (1) ab が 3 の倍数であるとき，a または b は 3 の倍数であることを示せ． (2) a + b と ab がともに 3 の倍数であるとき，a と b はともに 3 の倍数であることを示せ． (3) a + b と a2+ b2がともに 3 の倍数であるとき，a と b はともに 3 の倍数であることを示せ． ［10 神戸理系 2 番+(0)+(4) 追加］ p を 3 以上の素数，a, b を自然数とする．以下の問に答えよ． (0) 自然数 m, n に対し，mn が p の倍数ならば，m または n は p の倍数であることを示せ.(1) a + b と ab がともに p の倍数であるとき，a と b はともに p の倍数であることを示せ． (2) a + b と a2+ b2がともに p の倍数であるとき，a と b はともに p の倍数であることを示せ． (3) a2+ b2と a3+ b3がともに p の倍数であるとき，a と b はともに p の倍数であることを示せ． (4) 自然数 n に対して an+ bnと an+1+ bn+1がともに p の倍数であるとき，a と b はともに p の倍数であることを示せ． 問題 2 解答 2 ［98 一橋］ 正の整数 n を 8 で割った余りを r(n) とおく．正の整数の組 (a, b) は条件 0 < a− r(a) < 4 3r(b), 0 < b− r(b) < 4 3r(ab) をみたすとする． (1) a− r(a) と r(b) を求めよ． (2) a と b を求めよ． 問題 3 解答 3 ［06 大教大］ 二つの自然数が互いに素であるとは，二つの自然数の最大公約数が 1 であることをいう．三つの 自然数が互いに素であるとは，三つの自然数からどの二つの自然数を選んでも，その選んだ二つの 自然数が互いに素になることをいう．このとき，次の問に答えよ． (1) 任意の自然数 k に対して，連続する二つの自然数 k と k + 1 は，互いに素であることを示せ. (2) n を 3 以上の奇数とする．n2は奇数であるから，ある自然数 k があって，n2= 2k + 1 と表 せる．このとき三つの自然数 n, k, k + 1 は互いに素であることを示せ. (3) 三つの互いに素な自然数を三辺の長さとする直角三角形は無数にあることを示せ. 問題 4 解答 4 ［98 京大後期文系］ a, b, p, q はすべて自然数で， p2+ q2 a = pq b を満たしている． a と b の最大公約数が 1 のとき以下の問いに答えよ． (1) pq は b で割り切れることを示せ． (2) √a + 2b は自然数であることを示せ． 問題 5 解答 5 [09 神戸大後期理系] 自然数 n について，以下の問に答えよ． (1) 恒等式 (n2+ 1)− (n + 2)(n − 2) = 5 を利用して，n + 2 と n2+ 1 の公約数は 1 または 5 に限ることを示せ． (2) (1) を用いて，n + 2 と n2+ 1 が 1 以外に公約数をもつような自然数 n をすべて求めよ．
(3) (1),(2) を参考にして，2n + 1 と n2+ 1 が 1 以外に公約数をもつような自然数 n をすべて求 めよ. 問題 6 解答 6 ［98 お茶の水女子大］正の整数 k, l (k >= l) に対して 数列 {an}, {bn} を次のよ うに定義する． a1= k, b1= l n >= 1 について an+1= { bn (bn̸= 0 のとき) an (bn= 0 のとき) ，bn+1= { anを bnで割った余り (bn̸= 0 のとき) bn (bn= 0 のとき) (1) k = 1998, l = 185 について，{an}, {bn} をそれぞれ第 5 項まで計算せよ． (2) 任意の k, l, n について bn>= bn+1 (等号は bn= 0 のときに限る) を示せ． (3) 任意の k, l について bn = 0 となる n が存在することを示せ． (4) bn= 0 となる n について an が k と l の最大公約数になっていることを示せ．
3
素数
3.1
素数の定義と素因数分解
0 および±1 でない整数 a は少なくとも ±1 と ±a を約数に持つ．±1 および ±a 以外の約数を 「真の約数」ともいう． 定義 4 真の約数を持たない正の整数 a を 素数 という．これに対して真の約数を持つ整数を 合 成数 という． 整数 α をこれ以上分解できないところまで分解して， α =±p1e1p2e2· · · pmem の形にしたものを素因数分解という． p1, p2, · · · , pmは異なる素数，e1, e2, · · · , emは正の整数である．どのような整数も，因数分 解できしかも順序を除けばただ一通りである． 例えば，48 をどんな順で因数分解しても，素因数分解までいけば (順序以外は) 同じである． 48 = 22· 12 = 22· 22· 3 = 24· 3 48 = 3· 16 = 3 · 24 このことは次のようにまとめられる．この定理は算術の基本定理ともいわれる．高校数学ではこ れは証明なしに認めてよい． 定理 4 合成数を素数の積に分解することができる．かつ，その分解の結果は因数の順序をのぞ けば一通り (これを一意という) である． 証明 数学的帰納法で示す． (1) 最小の合成数は 4 で 4 = 2× 2 でありこれ以外にないから，成立． (2) a よりも小さい (正の) 整数については定理が成立していると仮定する． a の分解の可能性を示す． a は合成数であるから a = b× c (1 < b < a, 1 < c < a) と分解される．数学的帰納法の仮定により b も c も素数の積に分解されるので，a も素数の積に 分解される． a の分解の一意性を示す．a を素因数に分解して二つの分解 a = p1p2· · · pm= q1q2· · · qn を得たとする．定理 2 の (4) より，二つの整数の積が素数 p の倍数なら，因数のなかの少なくとも 一つがその素数の倍数である．三つ以上の数以上の積の場合も abc = (ab)c のように括弧でくくり 順次考えれば，いずれかが p の倍数になる．したがって，p1, p2, · · · , pmのいずれかは q1 の倍 数である．いま p1が q1 の倍数であるとすれば, p1 は素数なので, p1= q1 である． ∴ p2· · · pm= q2· · · qn この両辺の数を b とすれば b < a なので数学的帰納法の仮定からこの分解は順序を除いて一意で ある．よって a において定理が成立する． (3) (1)(2) より，任意の整数に対して定理が成立することが示された． (証明終わり)例 2 素因数分解が一通りであること用いた証明の例をあげよう．次の (1) と (2) を証明しよう． (1) は先の入試問題 1 の解答では，具体的に書いて済ませたところである．これを一般的に示す ときには以下のようにしなければならない．また (2) は，高校数学の教科書に書いてある方法とは 異なるものである．それぞれ次のように素因数分解の一意性を根拠に示される． (1) a と b を整数，p を素数とする．ab が p の倍数ならば，a または b が p の倍数である． (2) √2 は有理数ではない． (1) a が p で割り切れないとする．つまり a と p は互いに素であるとする．ab が p の倍数である から，定理 2 の (4) によって，b は p の倍数である． b が p で割り切れないときは a が p の倍数になる． (証明終わり) (2) 有理数であるとし，√2 = n mとおく．これから 2m2= n2 右辺 n2の因数分解のなかに素因数 2 は偶数個ある．左辺 2m2の因数分解のなかに素因数 2 は奇数個ある．これは素因数分解の一意性と矛盾する．よって√2 は有理数ではない．(証明 終わり) 定理 5 素数の数は無限である． 証明 背理法で示す．素数の個数が有限であると仮定する．その個数を n 個とし，p1, p2, · · · , pn をすべての素数とする．このとき a = p1p2· · · pn+ 1 とおく．定理 4 より a は素数の積に分解される． 一方 a は p1, p2, · · · , pn のいずれで割っても 1 余る．つまり，p1, p2, · · · , pn は a の約数でな い．よって a の素因数分解に現れる素数は p1, p2, · · · , pn ではあり得ず，それら以外の素数であ る．これは p1, p2, · · · , pn がすべての素数という仮定と矛盾する．ゆえに素数の数は無限である． (証明終わり) 人類史上はじめて背理法を用いて素数が無数にあることを示したのもまたエウクレイデスであ る．これと同じ内容の論証が『原論』に書かれている．
3.2
ピタゴラス数の一般形
x2+ y2= z2 を満たす正の整数の組 (x, y, z) をピタゴラス数という． x, y, z の最大公約数が 1 である組の一般形を求めてみよう． x, y がともに偶数なら z も偶数になって，最大公約数が 1 でなくなるので，x と y のいずれか は奇数である． y を偶数とする. x と z は奇数になる. y2= (z− x)(z + x)であるが， x と z は奇数なので， z− x, z + x はともに偶数である. つまり ( y 2 )2 = z + x 2 · z− x 2 · · · 1⃝ で， y 2, z + x 2 , z− x 2 がすべて整数になる. さらに， z + x 2 , z− x 2 がたがいに素になる．なぜならもしこの 2 数が公約数 d をもてば, z + x = 2du, z− x = 2dv となり,
z = d(u + v), x = d(u− v), y2= 4duv となって x, y, z の最大公約数が 1 であることに反する. z + x 2 , z− x 2 は互いに素で，かつその積が平方数である． 1 ⃝ の左辺を素因数分解すると，各素因数は偶数個現れる．z + x 2 , z− x 2 が互いに素なので，こ れらの素因数はそれぞれ z + x 2 , z− x 2 のいずれか一方にのみ現れ，その結果 z + x 2 , z− x 2 の素 因数分解で各素因数はすべて偶数個現れる． よってz + x 2 , z− x 2 はいずれも平方数である． z + x = 2a2, z− x = 2b2 とおく．これから x = a2− b2, y = 2ab, z = a2+ b2 となる． 最大公約数が 1 であるための a と b の条件を求める． a と b はたがいに素で a > b ，さらに x, z が奇数なので a と b の偶数奇数が異なることが， (x, y, z) の最大公約数が 1 であるために必要である. よって，最大公約数が 1 の解は (x, y, z) = (a2− b2, 2ab, a2+ b2), (2ab, a2− b2, a2+ b2) a > b, (a, b) = 1, a− b は奇数 . . . 2⃝ と表せる. 逆に条件 2⃝ を満たす a と b を用いて上のいずれかで表される (x, y, z) は最大公約数が 1 の 解である． それを示す． 2⃝ のように定まる x, y, z がピタゴラス数であることは明か． もしこの (x, y, z) に共通素因数 p があるとする.
すると z± x か z ± y を考えると p は 2a2, 2b2 の公約数である. a と b はたがいに素なので p = 2 である. ところが p = 2 が a2− b2 約数なので a2− b2= (a + b)(a− b) が偶数. これは条件 a− b は奇数 に反する. よって確かに 2⃝ で定まる (x, y, z) は，最大公約数が 1 の ピタゴラス数である． 必要条件とあわせて， 2⃝ で表される x, y, z が最大公約数が 1 のピタゴラス数のすべてである．
3.3
演習問題
問題 7 解答 7 [00 上智大] あ から え には下の選択肢 (a)，(b)，(c)，(d) から正しいものを選んで入れよ． (1) n を整数とする．n が 6 または 15 で割り切れることは， n が 30 で割り切れるための あ ． 1 <= n <= 300 をみたし，6 または 15 で割り切れる n は全部で ハ 個ある． (2) m, n を整数とする． m + n, mn がともに 12 で割り切れることは， m, n がともに 6 で割 り切れるための い ．1 <= m <= n <= 100 をみたし， m + n, mn がともに 12 で割り切れる m, n の組は全部で ヒ 個ある． (3) l, m, n を整数とする． l + m + n, lm + mn + nl, lmn がすべて 5 で割り切れることは， l, m, n がすべて 5 で割り切れるための う ． (4) l, m, n を整数とする． l + m + n, lm + mn + nl, lmn がすべて 30 で割り切れること は， l, m, n がすべて 30 で割り切れるための え ．1 <= l <= m <= n <= 100 をみたし， l + m + n, lm + mn + nl, lmn がすべて 30 で割り切れる l, m, n の組は全部で フ 個ある． 選択肢： (a) 必要十分条件である． (b) 必要条件であるが十分条件ではない． (c) 十分条件であるが必要条件ではない． (d) 必要条件でも十分条件でもない． 問題 8 解答 8 ［99 京大文後期］ 自然数 a , b , c について，等式 a2+ b2= c2が成り立ち，かつ a , b は互いに素とする．このと き，次のことを証明せよ． (1) a が奇数ならば，b は偶数であり，したがって c は奇数である． (2) a が奇数のとき， a + c = 2d2 となる自然数 d が存在する． （注）本問はピタゴラス数の一般形を求める定理の中の一部であるが，入試問題として紹介する．問題 9 解答 9 ［06 東京工大］ 自然数 a, b, c が 3a = b3, 5a = c2 を満たし，d6が a を割り切るような自然数 d は d = 1 に限るとする． (1) a は 3 と 5 で割り切れることを示せ． (2) a の素因数は 3 と 5 以外にないことを示せ． (3) a を求めよ． 問題 10 解答 10 ［09 千葉大］ (1) 5 以上の素数は，ある自然数 n を用いて 6n + 1 または 6n− 1 の形で表されることを示せ． (2) N を自然数とする．6N− 1 は，6n − 1 (n は自然数) の形で表される素数を約数にもつこと を示せ． (3) 6n− 1 (n は自然数) の形で表される素数は無限に多く存在することを示せ．
4
一次不定方程式
4.1
不定方程式の整数解
未知数が x と y，あるいは x, y, z など 2 個以上あり，係数が整数である方程式，例えば 2x + 3y = 1, xy− 2x − 3y + 1 = 0, 1 x+ 1 y + 1 z = 1, x 2− 3y2= 1 のようなものでは，実数の解は無数にある．解が定まらないので不定方程式という．ところが，こ れらの方程式を満たす整数の組となると，有限個であったり，すべてが書き下せたり，あるいは存 在しなかったり，さまざまに変化する．不定方程式の整数解すべてを求めることはできるのか．一 般的に書くことができるのか．これが整数の主要な問題の一つである． とくに一次不定方程式： 5x + 2y = 1, 7x− 5y = 3 の整数解が重要なテーマである．5x + 2y = 1 の整数解という問題では · · · , 5(−2) + 2(3) = 1, 5(1) + 2(−2) = 1, 5(3) + 2(−7) = 1, · · · といくつもある．すべての解を求める，あるいは解の一般形を求めるという問題が生まれる．さら に，5x + 2y = 1 は暗算で解が一組は求まったが， 37x + 13y = 1 となると，すぐには見いだせないし，そもそも解の存在からして明らかではない． どのような条件で解が存在するのか．一次不定方程式の解の存在条件と，すべての解を求める問 題を解決しよう．ここでそのうち重要な二つを紹介する．4.2
差で閉じた部分集合
一つの方法のための準備が次の定理である． 定理 6 整数からなる空でなく{0} でもない集合 A が次の条件を満たす． a, b∈ A ⇒ a − b ∈ A このとき集合 A はある整数 d の倍数の全体と一致する． 集合 A は差をとる演算に関して閉じている．整数からなる集合 A が差で閉じていれば，ある整 数 d が存在して A ={ dn | n : 整数 } と表されるということを意味している． 証明 条件から 0 = a− a ∈ A である．その結果，a ∈ A なら −a = 0 − a ∈ A である．また，自 然数 n に対して na∈ A のとき (n + 1)a = na− (−a) ∈ Aとなるので，数学的帰納法によって a∈ A なら na ∈ A である．このとき −na ∈ A でもあるので， 整数 n に対して na∈ A である． A の要素のうち正の要素からなる部分集合をとる．自然数の部分集合なので最小要素が存在す る．それを d とする．A の任意の要素 a をとり d で割る． a = dq + r 0 <= r < d とおく．d∈ A より dq ∈ A である．よって r = a − dq ∈ A である．ここでもし r > 0 なら d が正 で最小の要素であることに反する．よって r = 0，つまり A の任意の要素 a は d の倍数である．つ まり A⊂ { dn | n : 整数 } である． 逆に d∈ A なので，最初に示したように整数 n に対して nd ∈ A．つまり，A ⊃ { dn | n : 整数 } も成り立つ．よって A ={ dn | n : 整数 } が示された． (証明終わり) この定理の証明では，自然数の部分集合には最小の要素が存在することと除法の定理がもっとも カギとなるところで用いられている． 1 次不定方程式の解の存在 以上の準備のもと，次のことが示される． 定理 7 整数係数の方程式 ax + by = 1 について次のことが成り立つ． (1) 整数解が存在すれば a と b は互いに素である． (2) a と b が互いに素なら整数解が存在する． (1) を示す．整数解を m, n，a と b の最大公約数を d とし，a = da′, b = db′とおく． am + bn = d(a′m + b′n) = 1 d が 1 の約数となり d = 1．つまり a と b は互いに素である． (2) を示す．集合 A を A ={ px + qy | x, y ∈ Z } とおく．a = px1+ qy1，b = px2+ qy2が A に属せば a− b = p(x1− x2) + q(y1− y2)∈ A である．したがって A は整数の差で閉じた集合である. その結果定理 6 によって A は A に属する ある整数 d の倍数の全体となる．この d は A の要素なので d = px0+ qy0と表される． p = p· 1 + q · 0 ∈ A, q = p· 0 + q · 1 ∈ A なので p も q も d の倍数である．つまり d は p と q の公約数である．p と q は互いに素なので d = 1 である．よって方程式 px + qy = 1 には解 (x0, y0) が存在した． (証明終わり)
4.3
部屋割り論法
解の存在の証明には別の方法がある．その原理を説明する． 有限個のもののなかに，ある条件を満たすものが存在することを示す根拠としてよく用いられる のが鳩の巣原理とか部屋割り論法とかいわれる次の原理である．同等な二つの形が用いられる． (i) m 人を n 部屋に分けて入れる．m >= nq + 1 なら，q + 1 人以上入る部屋が存在する．(ii) n 人を n 部屋に相部屋にならないように振り分ける．各部屋に入るものが存在する． これを用いて定理 7(2) の証明をしよう．これは章末の演習問題 14 のように，入試問題でもよく 出題される．次の証明は演習問題 14 の (3)，(4) と同じ内容である． 部屋割り論法による定理 7(2) の証明 i = 0,· · · , b − 1 に対して ai を b で割った余りを ri とす る. 各 ri は 0 から b− 1 のどれかの値をとる．0 <= i, j <= b − 1 に対して ri と rj が ri = rj と する. ai = bqi+ ri aj = bqj+ rj より a(i− j) = b(qi− qj) a と b が互いに素なので i− j が b の倍数である. 0− (b − 1) <= i − j <= b − 1 − 0 より，この範囲の b の倍数は，i− j = 0 以外にない. 対偶をとると, i̸= j =⇒ ri̸= rj 0 <= i <= b − 1 の b 個の i に対して，同じ範囲の値 riが対応し，これらのうちに同じ値がない．鳩 の巣原理によって ri (0 <= i <= b − 1) は 0 から b − 1 の各値を一つずつとる． k を b で割って商が q，余りが s とする．ri= s となる i が存在する．つまり ai = bqi+ s となる i と qiが存在する．s = k− bq なので ai + b(q− qi) = k つまり (x, y) = (i, q− qi) が ax + by = k の解である. (証明終わり) 1 次不定方程式の一般解 演習問題 14(2) は次のように一般的に成り立つ． 定理 8 a と b を互いに素な整数とし，不定方程式 ax + by = 1 の 1 つの整数解を x0, y0 とする．すべての整数解は次のように与えられる． (x, y) = (x0+ bt, y0− at), (t は任意の整数) 証明 任意の整数解 x と y をとる．ax + by = 1 と ax0+ by0= 1 の辺々を引く． a(x− x0) + b(y− y0) = 0 a と b が互いに素なので，x− x0は b の倍数．これを bt とおく．このとき x = x0+ bt, y = y0− at となる． 逆にある整数 t を用いてこの形に表される x と y は不定方程式を満たす．よって定理が示され た． (証明終わり) このよう一般的な形で表された解を一般解という．これは，直線 ax + by = 1 上には無数の格子 点が等間隔に乗っていること，それらを一般的な形に書くことができることを意味している．
4.4
解の発見法
解が存在することはわかった．しかし係数が大きいと一組見つけるのは大変だ．3x + 2y = 1 な ら暗算でできる．しかし 127x + 52y = 1 となると，一組見つけるのも暗算というわけにはいかな い．ところが，ユークリッドの互除法を用いて一組の解を構成する一般的な方法がある． a と b の最大公約数が 1 より大きいとき，k が，a と b の最大公約数の倍数でなければ解はな い．k が最大公約数の倍数なら全体をその最大公約数で割って，初めから a と b の最大公約数は １，つまり a と b は互いに素であるとしてよい．このとき ax + by = 1 に解が見つかれば x と y の各々に k を乗じることにより，ax + by = k の解ができる．結局 a と b が互いに素なときに ax + by = 1 の解が構成できればよいことがわかる． (1) a > b とし，a = bq + r, (0 <= r < b) とする． (2) ax + by = (bq + r)x + by = rx + b(qx + y) であるから，y′= qx + y とおくと方程式 ax + by = 1 は方程式 rx + by′= 1 となる．(3) rx+by′ = 1 の解 (x0, y′0) が構成できれば，y0= y′0−qx0によって定めた (x0, y0) が ax+by = 1
の解となる． a と b が互いに素なら b と r も互いに素であるから，こうして係数のより小さい方程式が得ら れ，しかもその解からもとの方程式の解が構成できる．この過程を繰り返すと，最後は係数の一方 は 1 となる． sx + y = 1 または x + ty = 1 の解として (0, 1) か (1, 0) をとれる．ここから逆に戻っていけば ax + by = 1 の解が得られる． この方法で 127x + 52y = 1 の解を構成しよう．まず互除法で方程式を変換する． (1) 127x + 52y = 1 (2) 127 = 52· 2 + 23 , y′= 2x + y , 23x + 52y′ = 1 (3) 52 = 23· 2 + 6 , x′= x + 2y′, 23x′+ 6y′= 1 (4) 23 = 6· 3 + 5 , y′′= 3x′+ y′, 5x′+ 6y′′= 1 (5) 6 = 5· 1 + 1 , x′′= x′+ y′′, 5x′′+ y′′= 1 ここから逆に解を構成していく． (1) (x′′, y′′) = (0, 1) (2) x′′= x′+ y′′より (x′, y′′) = (−1, 1) (3) y′′= 3x′+ y′ より (x′, y′) = (−1, 4) (4) x′ = x + 2y′ より (x, y′) = (−9, 4) (5) y′= 2x + y より (x, y) = (−9, 22) 確かに, 127· (−9) + 52 · 22 = −1143 + 1144 = 1 である．これは二変数の不定方程式の解を構成 する一般的な方法である．
注意 1 この方法はまた，解の存在の証明にもなっている．a と b が互いに素なら，上記のよう にユークリッドの互除法をくりかえすことで，5x′′+ y′′= 1 のように一方の係数が 1 の不定方程 式が得られる．これは 0 と 1 の組みという整数解が存在し，これからもとの方程式の整数解の存在 が示される．
4.5
演習問題
問題 11 解答 11 ［80 京大理系］ 互いに異なる n 個（n >= 3）の実数の集合 S = {a1, a2,· · · , an} が次の性質をもつという． 「S から相異なる要素 ai，aj をとれば ai− aj，aj− ai の少なくとも一方は必ず S に 属する」 このとき， (1) 次の 2 つのうちのいずれか一方が成り立つことを示せ． （イ）ai>= 0 (i = 1, 2, · · · , n) （ロ）ai<= 0 (i = 1, 2, · · · , n) (2) a1, a2, · · · , an の順序を適当に変えれば等差数列になることを示せ． 問題 12 解答 12 ［85 お茶の水女子大］ 自然数を要素とする空集合でない集合 G が次の条件 (i),(ii) を満たしているとする． (i) m, n が G の要素ならば，m + n は G の要素である． (ii) m, n が G の要素で m > n ならば，m− n は G の要素である． このとき G の最小の要素を d とすると G ={kd | k は自然数 } であることを証明せよ． 問題 13 解答 13 ［99 京大文前期改題］ ※原題は「下 3 桁」が「下 2 桁」．及び (3) は追加． 0 以上の整数 x に対して, C(x) で x の下 3 桁を表すことにする．たとえば， C(12578) = 578, C(6) = 6 である．n を 2 でも 5 でも割り切れない正の整数とする．(1) x，y が 0 以上の整数のとき，C(nx) = C(ny) ならば，C(x) = C(y) であることを示せ． (2) C(nx) = 1 となる 0 以上の整数 x が存在することを示せ． (3) C(397x) = 1 となる 0 以上の整数 x で最小のものを求めよ． 問題 14 解答 14 ［00 大阪女子大］ a, b は互いに素な正の整数とする． (1) 4m + 6n = 7 を満たす整数 m, n は存在しないことを示せ． (2) 3m + 5n = 2 を満たすすべての整数の組 (m, n) を求めよ． (3) k を整数とするとき， ak を b で割った余りを r(k) で表す．k, l を b− 1 以下の正の整数と するとき， k̸= l ならば r(k) ̸= r(l) であることを示せ．
(4) am + bn = 1 を満たす整数 m, n が存在することを示せ． 問題 15 解答 15 ［00 京大理系後期］ xy 平面上の点で x 座標， y 座標がともに整数である点を格子点という． a, k は整数で a >= 2 とし，直線 L : ax + (a2+ 1)y = k を考える． (1) 直線 L 上の格子点を一つ求めよ． (2) k = a(a2+ 1) のとき， x > 0, y > 0 の領域に直線 L 上の格子点は存在しないことを示せ． (3) k > a(a2+ 1) ならば， x > 0, y > 0 の領域に直線 L 上の格子点が存在することを示せ． 問題 16 解答 16 ［08 名大理系］ 次の問いに答えよ． (1) 3x + 2y <= 2008 を満たす 0 以上の整数の組 (x, y) の個数を求めよ． (2) x 2 + y 3 + z 6 <= 10 を満たす 0 以上の整数の組 (x, y, z) の個数を求めよ． 問題 17 解答 17 ［12 山梨大後期］ f (m, n) = m2− mn + n2とおく．自然数 k に対して，平面上の点 (m, n) の集合 X(k) ={(m, n) | m, n は整数，f(m, n) = k } を考える． (1) X(k) は有限集合であることを示せ．また，X(1) の要素をすべて求めよ． (2) k = 2, 4 に対して，X(k) の要素の個数をそれぞれ求めよ． (3) 自然数 r に対して，X(2r) の要素の個数を求めよ．
5
余りによる類別
5.1
整数の合同
整数 a と b の差が m の倍数であるとき, a と b は m を法として互いに合同である． といい，次のように記す． a≡ b (mod. m) 次のことは高校数学範囲では証明なしに用いてよい．しかしまた，証明されることであることも 知っておこう． 定理 9 2 整数 a と b が m を法として合同であることと，a と b を m で割った二つの余りが等し いことは同値である． 証明 a と b が m を法として合同であるとする．a− b = mq とおける．a と b を m で割った商 と余りをそれぞれ q1, q2 ，r1, r2 とする． a = mq1+ r1, b = mq2+ r2 2 式の辺々を引いて a− b = mq を用いると mq = (q1− q2)m + r1− r2 つまり |m||q − q1+ q2| = |r1− r2| もし q− q1+ q2̸= 0 なら，|m||q − q1+ q2| >= |m| であるが，右辺は m で割った余りの差なので |r1− r2| < m となり矛盾する． ∴ q− q1+ q2= 0， r1− r2= 0 逆に a と b を m で割った余りが等しいとする． a = mq1+ r, b = mq2+ r より a− b = m(q1− q2) である．つまり a と b は m を法として合同である． (証明終わり)5.2
剰余系
整数の集合Z において，m を法として互いに合同な整数で一つの部分集合を作り，合同でない ものは異なる部分集合になるようにして，Z を互いに共通部分のない，いくつかの部分集合の和に することができる． なぜうまく分けられるのだろうか．合同であるという関係は，等号や図形の相似や合同などと同 じく，次の三つの規律に従う． 反射律 : a≡ a (mod. m) 対称律 : a≡ b (mod. m) ならば b ≡ a (mod. m)これがあるので，互いに合同な数どうしを一組の部分集合にすることが出来る． 一つ一つの部分集合を m を法とする類，あるいは剰余類といい，類に分けることを類別という． m を法とする類とは, m を法として互いに合同なすべての数の集合である．いいかえると m で割っ たとき余りの等しい整数の集合である．よって m を法とする類別では m 個の類に類別される． 各集合について，その集合に属する一つの要素 a をとれば，同じ集合に属するすべての要素は， 整数 k を用いて mk + a と表される． m を法として m 個に分けられた各集合から一つずつ代表を取り出したとき，それを完全な代表 の一組 (または剰余系) という．例えば {0, 1, 2, 3, 4, 5, 6} {0, 1, 2, 3, −3, −2, −1} {7, −6, 9, −4, −10, −9, 13} はいずれも 7 を法とする完全な代表の一組になっている．
5.3
合同式
合同であることを示す関係式 a≡ b (mod. m) は，整数の和差積に関して，等式の場合と同じ く次のことが成り立つ． 定理 10 以下，各文字は整数を表す． a≡ a′ (mod. m), b≡ b′ (mod. m) ならば a± b ≡ a′± b′ (mod. m), ab≡ a′b′ (mod. m) (1) である．一般に a≡ a′ ( mod . m), b≡ b′ ( mod . m), c≡ c′ ( mod . m), · · · で f(x, y, z, · · ·) がx, y, z, · · · に関する整数係数の整式ならば
f (a, b, c, · · ·) ≡ f(a′, b′, c′, · · ·) (mod. m) (2) 証明 仮定によって a−a′および b−b′は m の倍数である．ゆえに (a+b)−(a′+b′) = (a−a′)+(b−b′)
は m の倍数である．また, ab− a′b′= (a− a′)b + a′(b− b′) も m の倍数である．すなわち (1) が 示された． (1) から a≡ a′ (mod. m) なら次のことが成り立つ． 1) 任意の整数 N に対して N a≡ Na′ (mod. m)． 2) 数学的帰納法と組みあわせて自然数 α に対し aα≡ a′α (mod. m)． ふたたび (1) から N aαbβcγ· · · ≡ Na′αb′βc′γ· · · (mod. m) である． もういちど (1) から∑N aαbβcγ· · · ≡∑N a′αb′βc′γ· · · (mod. m) となり (2) が示された． (証 明終わり) 合同式に関する二つの定理を紹介する． 第一は数の等式での命題 ab = ac かつ a̸= 0 ならば b = c に対応するものである． 定理 11 ac≡ bc (mod. m) かつ (c, m) = 1 ならば a ≡ b (mod. m)
証明 仮定から ac− bc は m の倍数つまり整数 N で ac − bc = (a − b)c = mN となるものがあ る．m と c は互いに素なのでこれから a− b が m の倍数であることがわかる．つまり a≡ b (mod. m) が示された． (証明終わり) 第二は，逆数の存在に関するものである． 定理 12 a と m が互いに素なとき ax≡ 1 (mod. m) となる整数 x が存在する． 証明 a と m が互いに素なので，一次不定方程式 ax + my = 1 は整数解 (x, y) = (α, β) をもつ． aα = 1− mβ ≡ 1 (mod. m) なので x = α が条件を満たす整数である． (証明終わり) 注意 2 ここは高校数学範囲を越えることであるが，定理 10 の意味は，2 つの剰余類からそれぞ れそこに属する整数をとりだし，その加法や乗法をおこなうと，その和や積の属する剰余類は，と りだした整数によらず確定する，ということである．この結果，剰余類の間に加法や乗法を定める ことができる．合同式 (1) は，このようにつかんではじめてその意味がわかる．
5.4
演習問題
問題 18 解答 18 ［01 京大文系前期］ 任意の整数 n に対し， n9− n3 は 9 で割り切れることを示せ． 問題 19 解答 19 ［03 千葉大 5 番］ 正の整数 x，y，z，n に対して x2= 72n(y2+ 10z2) が成立しているとする． (1) 整数の 2 乗を 3 でわった余りは 0 か 1 であることを示せ． (2) yz は 3 の倍数であることを示せ． (3) y，z がともに素数のとき x を n を用いて表せ． 問題 20 解答 20 [82 九大] 整数を係数とする n 次の多項式 f (x) = xn+ a1xn−1+· · · + an−1x + an (n > 1) について次のことを証明せよ． (1) 有理数 α が方程式 f (x) = 0 の１つの解ならば， α は整数である． (2) ある自然数 k(> 1) に対して， k 個の整数 f (1), f (2),· · · , f(k) のどれもが k で割り切れ なければ方程式 f (x) = 0 は有理数の解をもたない．6
フェルマの小定理
6.1
オイラーの関数
自然数 1, 2, · · · , n のなかにある n と互いに素な整数 x の個数を φ(n) で表す．例えば， φ(1) = 1, (x = 1) φ(2) = 1, (x = 1) φ(3) = 2, (x = 1, 2) φ(4) = 2, (x = 1, 3) φ(5) = 4, (x = 1, 2, 3, 4) φ(6) = 2, (x = 1, 5) この φ(n) をオイラーの関数という．これは自然数を定義域とする関数である．p が素数ならば，明 らかに φ(p) = p− 1 である． 入試問題 21 のように，オイラーの関数を題材とする問題がある．まずこれを解いてみよう．こ の問題の (2) の解は異なる素数 p と q に対して φ(pq) = φ(p)φ(q) が成り立つことを意味している． 一般的に次のことが成り立つ． 定理 13 a と b が互いに素ならば，φ(ab) = φ(a)φ(b) である． 証明 m = φ(a) とし，α1, α2, · · · , αmを 1 以上 a 以下で a と互いに素な整数とする．n = φ(b) とし，β1, β2, · · · , βn もまた同様に選ばれているとする． αi, βjの組は mn = φ(a)φ(b) 個ある．その一つをとる．a と b が互いに素なので ak + αi= bl + βj となる整数 k と l がとれる．この式の値は，αiが a と互いに素なので a と互いに素で，βjが b と 互いに素なので b と互いに素．つまり ab と互いに素である． この式の値を ab で割った余りを γijとする．γijは γij ≡ αi (mod. a) , γij ≡ βj (mod. b) となる 1 以上 ab 以下の数である．i を i′に変え同様にして γi′jをとる．γij ≡ ak + αi (mod. a)，γi′j ≡ ak′+ αi′ (mod. b) よ
り γijと γi′jは a を法として合同でない．よって ab を法として合同でない．j が異なる場合も，両 方異なる場合も同様である．ab と互いに素で互いに合同でない整数が少なくとも mn 個存在した． つまり φ(a)φ(b) <= φ(ab) 逆に (γ, ab) = 1 とすると，γ が a とも b とも互いに素なので a を法として αiに, b を法として βjに合同となる i, j が存在する．γ と γ′が ab に関して合同でなければ a または b の少なくとも 一方に関しても合同でない．よって異なる γ に対する αi, βjの組はすべて異なる． φ(a)φ(b) >= φ(ab) あわせて等号が成立し定理が示された． (証明終わり)
例 3 a = 14, b = 15 として上記の推論をたどってみよう． φ(14) = φ(2)φ(7) = 6, φ(15) = φ(3)φ(5) = 8 であり，それぞれ αi, βjとして α1= 1, α2= 3, α3= 5, α4= 9, α5= 11, α6= 13 β1= 1, β2= 2, β3= 4, β4= 7, β5= 8, β6= 11, β7= 13, β8= 14 である．α4= 9, β6= 11 をとってみよう． 14k + 9 = 15l + 11 となる整数 k と l は k =−2, l = −2 がとれる．式の値が −19 なので γ46= 210− 19 = 191 である． 191≡ 9 (mod. 14) , 191 ≡ 11 (mod. 15) となっている．191 は確かに ab = 210 と互いに素である． α6= 13, β5= 8 をとってみよう． 14k + 13 = 15l + 8 となる整数 k と l は k = 5, l = 5 がとれる．式の値が 83 なので γ65= 83 である． 83≡ 13 (mod. 14) , 83 ≡ 8 (mod. 15) となっている．これは確かに ab = 210 と互いに素である． そして 191 と 83 については 191− 83 = 108 は ab の倍数ではないので ab を法として合同でない． このようにして得られる 6· 8 = 48 個の γij が 1 以上 210 以下で 210 と互いに素な数の全体と なる．
6.2
フェルマの小定理
定理 14 n を正整数，a を n と互いに素な整数とする．このとき次式が成り立つ． aφ(n)≡ 1 (mod. n) 証明 α1, α2, · · · , αm, m = φ(n) を n と互いに素で，相互に n を法として合同でない整数とする．a が n と互いに素なので，aαi, aαjが n に関して合同になるのは αi, αjが合同なときにかぎ
る．よって aα1, aα2, · · · , aαmは n と互いに素でかつ互いに合同でない整数である．
n と互いに素でかつ互いに合同でない整数の個数が m なので，aα1, aα2, · · · , aαmのそれぞれ
は α1, α2, · · · , αmのそれぞれ 1 つずつと n を法として合同である．よってその積は n を法とし
て互いに合同である．
aα1· aα2· · · aαm = am· α1· · · αm
≡ α1· · · αm (mod. n)
α1· · · αmは n と互いに素なので，
である． (証明終わり) n が素数のときは φ(p) = p− 1．したがって p と互いに素な a に対して ap−1≡ 1 (mod. p) である．これをフェルマの小定理という．これをそのまま入試問題としたものもある． また，a が p と互いに素であるという条件をとり，任意の整数 a とすると， ap≡ a (mod. p) が成り立つ．
6.3
演習問題
問題 21 解答 21 ［03 名大改題 (3) 追加］ n を自然数とするとき，m <= n で m と n の最大公約数が 1 となる自然数 m の個数を f (n) と する． (1) f (15) を求めよ． (2) p, q を互いに素な素数とする．このとき f (pq) を求めよ． (3) p を素数，e を自然数とする．このとき f (pe) を求めよ． 問題 22 解答 22 ［06 横浜市大 2 番］ N を自然数とし，ϕ(N ) を N より小さくかつ N と互いに素な自然数の総数とする．すなわち ϕ(N ) = ♯{n | n は自然数，1 <= n < N ，gcd(N, n) = 1 } で，オイラー関数と呼ばれている．ここに gcd(a, b) は a と b の最大公約数を，♯ A は集合 A の 要素の総数を意味する．例えば， ϕ(6) = ♯{1, 5} = 2, ϕ(15) = ♯ {1, 2, 4, 7, 8, 11, 13, 14} = 8 である．このとき以下の問いに答えよ． (1) p と q を互いに異なる素数とし N = pq とおく． (i) N より小さい自然数 n で，gcd(N, n)̸= 1 となるものを全て求めよ． (ii) ϕ(N ) を求めよ． (2) p と q を互いに異なる素数とし N = pq とおく．今 N と ϕ(N ) があらかじめわかつていると き，p と q を解としてもつ二次方程式を N や ϕ(N ) 等を用いて表せ． (3) N = 84773093 および ϕ(N ) = 84754668 であるとき，N = pq (p > q) となる素数 p および q を求めよ (求めた p および q が素数であることを示さなくてよい)． ただし, 必要に応じて以下の数表を使つてもよい． 3202= 102400；3222= 103684；3242= 104976； 3262= 106276；3282= 107584；3302= 108900問題 23 解答 23 ［95 京大文系後期］ 自然数 n の関数 f (n), g(n) を f (n) = n を 7 で割った余り g(n) = 3f ( 7 ∑ k=1 kn ) によって定める. (1) すべての自然数 n に対して f (n7) = f (n) を示せ. (2) あなたの好きな自然数 n を一つ決めて g(n) を求めよ. その g(n) の値をこの設問 (2) におけ るあなたの得点とする． 問題 24 解答 24 ［東京農大］ p を素数，n を p で割り切れない自然数とし，1 から p− 1 までの自然数の集合を A とおく． (1) 任意の k∈ A に対し，nk を p で割った余りを rkとする．このとき，集合{rk | k ∈ A} は A と一致することを示せ． (2) np−1− 1 は p で割り切れることを示せ． 問題 25 解答 25 ［奈良女子大改題］ (1) 素数 p と 1 <= r <= p − 1 なる整数 r に対して, 二項係数についての等式 rpCr= pp−1Cr−1 を 証明し,pCrは p の倍数であることを示せ. (2) 素数 p に対して 2p を p で割った余りを求めよ. (3) 自然数 n に対して np を p で割った余りを推測し, 数学的帰納法で証明せよ. 問題 26 解答 26 ［10 阪大後期］ p は素数，r は正の整数とする．以下の問いに答えよ. (1) x1, x2, · · · , xrについての式 (x1+ x2+· · · + xr)pを展開したときの単項式 x1p1x2p2· · · xrpr の係数を求めよ．ここで，p1, p2, · · · , prは 0 または正の整数で p1+ p2+· · · + pr= p をみ たすとする. (2) x1, x2, · · · , xrが正の整数のとき， (x1+ x2+· · · + xr)p− (x1p+ x2p+· · · + xrp) は p で割り切れることを示せ． (3) r は p で割り切れないとする．このとき，rp−1− 1 は p で割り切れることを示せ．
7
整式の整数論
7.1
整式の除法
以上の議論は整式の場合にもそのままあてはまる．実数係数の整式の集合を変数を明示してR[x] と表そう．また係数を有理数にかぎるときはQ[x] と表す．以下のことは R[x] で考えても，Q[x] で 考えても，また複素数で考えC[x] としても同じことである．そこで K を有理数の集合 Q，実数の 集合R，複素数の集合 C のいずれかを表すものとし，これからは K に係数をもつ整式の集合 K[x] を考えることにしよう． x の整式は，つぎの除法の基本性質をもつ．ここで deg f (x) は整式 f (x) の次数を表す． 定理 15 整式 f (x), g(x) (deg g(x) >= 1) がある． f (x) = g(x)· q(x) + r(x) , 0 <= deg r(x) < deg g(x) となる整式 q(x), r(x) がただ１組存在する． 証明 deg f (x) = n, deg g(x) = m とする．条件を満たす q(x) と r(x) の存在を n についての数学 的帰納法で示す． n < m なら q(x) = 0, r(x) = f (x) で成立．0 から n− 1 で成立とする． f (x) と g(x) の n, m 次の項をそれぞれ axn, bxm とする． f1(x) = f (x)− a bx n−mg(x) と定めれば, deg f1(x) < deg f (x) である．帰納法の仮定から， f1(x) = g(x)· q1(x) + r1(x), 0 <= deg r1(x) < deg g(x) となる q1(x), r1(x) が存在する． f (x) = g(x)a bx n−m+ f 1(x) = g(x)a bx n−m+ g(x)· q 1(x) + r1(x) = g(x) { a bx n−m+ q 1(x) } + r1(x) となるので，q(x) = a bx n−m+ q 1(x)，r(x) = r1(x) とおけば定理の等式を満たす． これが１組しかないことを示す．2 組あったとする． f (x) = g(x)· q1(x) + r1(x) = g(x)· q2(x) + r2(x) すると， g(x)· {q1(x)− q2(x)} = r2(x)− r1(x) となる．もし q1(x)− q2(x)̸= 0 なら deg(r2(x)− r1(x)) >= deg g(x) である．ところが一方，deg r1(x) < deg g(x), deg r2(x) < deg g(x) だから，deg(r2(x) − r1(x)) <
deg g(x)．これは矛盾．
