整数の性質 ★ 基礎の問題 全12問

方針

解答

⓪ 発想(どう考え始めるか) 倍数の判定法は、どこを見るかが数によって違う。ここを取り違えないことがすべてだ。

• $3$ の倍数・$9$ の倍数 → 各位の数字の和を見る
• $4$ の倍数 → 下 $2$ 桁だけを見る
• $2$・$5$ の倍数 → 一の位だけを見る

(1) $837$ の各位の和は $8+3+7=18$。$18$ は $9$ の倍数だから、$837$ も $9$ の倍数。$9$ の倍数は自動的に $3$ の倍数でもある。

(2) $4$ の倍数は下 $2$ 桁で決まる。上の $31$ は関係ない。$\square 4$ が $4$ の倍数になる $\square$ を探せばよい。

(3) $5+\square +2=7+\square$ が $9$ の倍数。$\square$ は $0$〜$9$ の $1$ 桁だから、和は $7$〜$16$ の範囲に収まり、$9$ しかありえない。

(1) $3$ の倍数・$9$ の倍数は、各位の数字の和で見分けられる。$837$ の各位の和は

$$8+3+7=18$$

$18$ は $9$ の倍数(だから $3$ の倍数でもある)。よって $837$ は $3$ の倍数でも $9$ の倍数でもある。(なぜ和で判定できるのか。$837=8\times 100+3\times 10+7$ で、$100=99+1$、$10=9+1$。$99$ と $9$ は $9$ の倍数だから、$837$ を $9$ で割った余りは『各位の和 $8+3+7$ を $9$ で割った余り』と同じになる。)

(2) $4$ の倍数かどうかは、下2桁だけで決まる($100$ が $4$ の倍数なので、百の位から上は $4$ で割り切れる)。$\overline{31\square 4}$ の下2桁は $\overline{\square 4}$。これが $4$ の倍数になる $\square$ を探す。$04,14,24,\dots ,94$ のうち $4$ で割り切れるのは $04,24,44,64,84$。よって

$$\square =0,2,4,6,8$$

(3) $\overline{5\square 2}$ の各位の和は $5+\square +2=7+\square$。$\square$ は $0$〜$9$ なので、$7+\square$ は $7$〜$16$。この中の $9$ の倍数は $9$ だけなので $7+\square =9$、つまり

$$\square =2$$

発展。 ここで使った「$10=9+1$ と分解する」という技は、合同式という記号を使うとずっと簡潔になる。

$$10\equiv 1(\mathrm{mod}9)$$

(「$10$ を $9$ で割った余りは $1$」と読む。) 合同式は掛け算・足し算がそのままできるので

$$10^2\equiv 1^2=1,10^3\equiv 1,\dots (\mathrm{mod}9)$$

したがって

$$837=8\cdot 10^2+3\cdot 10+7\equiv 8+3+7=18\equiv 0(\mathrm{mod}9)$$

$3$ 行で証明が終わる。

$4$ の判定なら $10^2=100\equiv 0(\mathrm{mod}4)$ を使えば、百の位から上が丸ごと消える。「余りだけを追いかける」という発想で、桁の話がすぐに片づく。

合同式はこの単元(整数の性質)全体を貫く道具である。倍数判定、余りの分類、不定方程式、$n$ 進法は、すべて「余り」についての話だ。$1$ つの記号がバラバラに見えた話を $1$ 本につないでくれる。

別解

なぜ「各位の和」で $9$ の倍数が分かるのか。なぜ $4$ は「下 $2$ 桁」なのか。 理由を知れば、判定法は暗記事項でなくなる。忘れてもその場で作り直せる。

$9$ の判定法のからくり。

$837$ を位ごとにばらす。

$$837=8\times 100+3\times 10+7$$

ここで $100=99+1$、$10=9+1$ と書きかえる。

$$837=8\times (99+1)+3\times (9+1)+7=\underset{\text{必ず 9 の倍数}}{\underbrace{(8\times 99+3\times 9)}}+\underset{\text{各位の和}}{\underbrace{(8+3+7)}}$$

前半は問答無用で $9$ の倍数($99$ も $9$ も $9$ の倍数だから)。だから $837$ が $9$ の倍数かどうかは、後半の「各位の和」だけで決まる。

$$8+3+7=18(\text{9 の倍数})⟹837\text{は 9 の倍数}$$

$99,999,9999,\dots$ はすべて $9$ の倍数なので、この理屈は何桁でも通用する。「$10$ を $9$ で割ると $1$ 余る」という $1$ つの事実が判定法の根拠だ。

$4$ の判定法のからくり。

こちらは $100$ に注目する。$100=4\times 25$ は $4$ の倍数だ。

$$3134=\underset{\text{必ず 4 の倍数}}{\underbrace{31\times 100}}+\underset{\text{下 2 桁}}{\underbrace{34}}$$

百の位から上は、$100$ が掛かっているので全部 $4$ の倍数。だから $4$ の倍数かどうかは下 $2$ 桁だけで決まる。上の桁が何であろうと関係ない。

これで(2)が解ける。$\square 4$ が $4$ の倍数になるのは

$$04,24,44,64,84⟹\square =0,2,4,6,8$$

同じ理屈で、判定法が次々に作れる。

• $8$ の倍数: $1000=8\times 125$ が $8$ の倍数 → 下 $3$ 桁を見る
• $2$・$5$ の倍数: $10$ が $2$ でも $5$ でも割れる → 下 $1$ 桁を見る
• $3$ の倍数: $10$ を $3$ で割ると $1$ 余る($9$ と同じ理屈)→ 各位の和

$11$ の倍数も見てみる。$10$ を $11$ で割ると $-1$ 余ると考えると、一の位から交互に $+,-$ して足した和($8-3+7$ のような)で判定できる。$837$ なら $7-3+8=12$ で $11$ の倍数ではない、と分かる(実際 $837=11\times 76+1$)。

判定法は「$10$ のべきを、その数で割った余り」から生まれる。 覚えるべきは $5$ 個の判定法ではなく、この $1$ つの仕組みである。

方針

解答

⓪ 発想(どう考え始めるか) 素因数分解は、小さい素数から順に、割り切れなくなるまで割る。手順は決まっている。

$$2\to 3\to 5\to 7\to 11\to \dots$$

$2$ で割れるだけ割ってから $3$ へ、$3$ で割れるだけ割ってから $5$ へと進む。飛ばさず、戻らずに割っていく。注意する点は $2$ つある。

$1$ つ目: 素数でない数で割らない。 $4$ や $6$ で割ると、分解が途中で止まったり、素因数を見落としたりする。

$2$ つ目: 最後に残った数が素数かどうか、必ず確かめる。 $49$ を「もう割れない」と思って素数扱いすると、$7^2$ を見逃す。$49=7\times 7$ である。

どこまで試せばよいか。割る素数が $\sqrt{(\text{残った数})}$ を超えたら、残りは素数だと分かる。

(1) 小さい素数から順に割る。

$$360=2\times 180=2\times 2\times 90=2\times 2\times 2\times 45$$

$45$ はもう $2$ で割れない。次は $3$:$45=3\times 15=3\times 3\times 5$。$5$ は素数。まとめると

$$360=2^3\times 3^2\times 5$$

(2) 同じように $2$ から。

$$1176=2\times 588=2\times 2\times 294=2\times 2\times 2\times 147$$

$147$ は $2$ で割れない。$3$ で割ると $147=3\times 49$、そして $49=7\times 7$。よって

$$1176=2^3\times 3\times 7^2$$

(検算:$2^3\times 3\times 7^2=8\times 3\times 49=1176$。組み立て直して元に戻るか確かめると安心だ。)

発展。 「どんな分解の道を通っても同じ答えになる」という当たり前に見える事実には、素因数分解の一意性(算術の基本定理)という名前がついている。

$$2\text{以上のどんな整数も、素数の積として、順序を除いてただ 1 通りに書ける}$$

当たり前だと思うだろうか。 しかし、使う数の範囲を少し変えると、この性質はあっさり壊れる。たとえば「偶数だけの集まり」を考えると、$60=2\times 30=6\times 10$ となり、$2,30,6,10$ はどれもその中ではそれ以上分解できない数になる(この集まりに $3$ や $5$ はない)。分解が $2$ 通りできてしまうのだ。

整数で一意性が成り立つのは、$1$ つの定理として証明されるべき事実であって、当たり前ではない。約数の個数の公式も、最大公約数の求め方も、この一意性をもとにしている。

現代の暗号技術はこの定理を逆手にとっている。 $2$ つの大きな素数を掛けるのはすぐにできるが、その積を素因数分解するのはきわめて難しい。インターネットの通信を守る暗号(RSA暗号)は、この非対称性を利用している。

$300$ 桁の合成数を素因数分解するのは、現在の計算機では数万年かかる。素因数分解は簡単そうに見えて、実はきわめて難しい問題である。$1176$ を割る今回の計算も、この問題の小さな例になっている。

別解

知っている掛け算から分解していくやり方も紹介しよう。慣れると、小さい素数で順に割るより速い。そして「どこまで試し割りすればよいか」の理屈も押さえる。

別ルート: 覚えている積に分けて、そこから枝を伸ばす(樹形図)。

(1) $360$。 「$360=36\times 10$」はすぐ思いつく。あとはそれぞれを分解する。

$$360=36\times 10=(4\times 9)\times (2\times 5)=(2^2\times 3^2)\times (2\times 5)=2^3\times 3^2\times 5$$

$2$ の個数を数え間違えないこと。 $4$ から $2$ 個、$10$ から $1$ 個で、合わせて $3$ 個 → $2^3$。

どんな道を通っても、たどり着く答えは同じ。 $360=8\times 45=2^3\times (9\times 5)=2^3\times 3^2\times 5$ でも同じである。これは偶然ではなく、素因数分解の一意性という定理が保証している(下の発展を参照)。

(2) $1176$。 こちらは目星がつきにくいので、素直に $2$ で割っていく。

$$1176÷2=588,588÷2=294,294÷2=147$$

$147$ は奇数なので $2$ では止まり。次は $3$。各位の和が $1+4+7=12$ で $3$ の倍数だから割れる。

$$147÷3=49$$

ここが山場。$49$ を「割れない」と早合点しない。 $49=7^2$ である。

$$1176=2^3\times 3\times 7^2$$

どこまで試し割りすればよいか。$1176$ を分解するとき、$2,3,5,7,11,13,\dots$ とどこまで試せばよいのだろう。答えは $\sqrt{1176}\approx 34.3$ まで。$34$ 以下の素数($2,3,5,\dots ,31$)で全部割り切れなければ、残った数は素数だと確定する。

なぜ $\sqrt{n}$ で足りるのか。 もし $n$ が合成数なら $n=a\times b$($a\leqq b$、どちらも $2$ 以上)と書ける。ここで $a$ と $b$ の両方が $\sqrt{n}$ より大きいことはありえない(もしそうなら $a\times b>\sqrt{n}\times \sqrt{n}=n$ となって矛盾)。

つまり、合成数なら必ず $\sqrt{n}$ 以下の約数を持つ。 $\sqrt{n}$ まで探して見つからなければ、それは素数だ。

この事実は実用的に大きい。$1176$ を調べるのに $1175$ 回割る必要はなく、$34$ までの素数 $11$ 個を試すだけでよい。探索範囲が大きく縮む。素数判定のアルゴリズムはまずこの一手から始まる。

検算の習慣。 分解できたら、必ず掛け戻す。

$$2^3\times 3\times 7^2=8\times 3\times 49=24\times 49=1176$$

方針

解答

⓪ 発想(どう考え始めるか) 約数の問題は、まず素因数分解。話はそこからだ。

$$600=2^3\times 3\times 5^2$$

$600$ の約数とは $2$ を何個・$3$ を何個・$5$ を何個使うか、を決めて掛け合わせたもの。

• $2$ の使い方: $0,1,2,3$ 個 → $4$ 通り
• $3$ の使い方: $0,1$ 個 → $2$ 通り
• $5$ の使い方: $0,1,2$ 個 → $3$ 通り

独立に選べるので、掛けて

$$4\times 2\times 3=24(\text{個})$$

$0$ 個使う場合を忘れない。だから指数に $+1$ する。総和も同じ発想で「各素数の使い方の合計」を掛け合わせる。

まず素因数分解する。$600=2^3\times 3\times 5^2$。

(1) 約数は $2^a\times 3^b\times 5^c$ の形になる。$a$ は $0,1,2,3$ の $4$ 通り、$b$ は $0,1$ の $2$ 通り、$c$ は $0,1,2$ の $3$ 通り。どれも独立に選べるので

$$4\times 2\times 3=24(\text{個})$$

『$0$ 個(その素数を使わない)』も1通りに数えるのがポイントだ。

(2) 約数の総和は各素因数について『$0$ 乗から最大乗までの和』を作り、それらをかけ合わせると出る。

$$(1+2+4+8)(1+3)(1+5+25)=15\times 4\times 31=1860$$

(なぜかけ算でよいのか。この積を展開すると、$2^a\times 3^b\times 5^c$ の形の項が『約数の選び方の分だけ』ちょうど1回ずつ現れる。つまり全約数の和そのものになる。)

発展。 約数の総和を $\sigma (n)$ と書く。$\sigma (600)=1860$ である。

この関数には、$2000$ 年以上前から人を惹きつけてきた問題がある。自分自身を除いた約数の和が、ちょうど自分自身になる数を、完全数という。

$$6=1+2+3,28=1+2+4+7+14$$

($\sigma$ で書けば $\sigma (6)=12=2\times 6$、$\sigma (28)=56=2\times 28$。)次の完全数は $496$、その次は $8128$。ユークリッドは「$2^{p-1}(2^p-1)$ で $2^p-1$ が素数なら完全数」と証明した($p=2$ で $6$、$p=3$ で $28$)。そして、$2000$ 年経った今も解けていない問題がある。

• 奇数の完全数は存在するか?($1$ つも見つかっていないが、存在しない証明もない)
• 完全数は無限にあるか?(現在 $50$ 個程度しか知られていない)

小学生でも意味が分かる問いが、$2000$ 年以上たった今も解かれていない。 整数論とはそういう分野だ。$600$ の約数を数える今回の作業も、この未解決問題と同じ「約数の和」を扱っている。簡単に見える問いほど、解くのが難しいことがある。

別解

部品ごとに計算して、最後に掛ける。この見方をすると、総和の公式が自然に理解できる。$600$ を、$3$ つの独立な部品に切り分ける。

$$600=\underset{2^3}{\underbrace{8}}\times \underset{3^1}{\underbrace{3}}\times \underset{5^2}{\underbrace{25}}$$

この $3$ つは互いに素(共通の素因数がない)。それぞれの約数の総和を、単独で計算する。

• $8$ の約数: $1,2,4,8$ → 総和 $15$
• $3$ の約数: $1,3$ → 総和 $4$
• $25$ の約数: $1,5,25$ → 総和 $31$

掛ける。

$$15\times 4\times 31=60\times 31=1860$$

これが答え。$24$ 個の約数を全部書き出して足す必要はない。

なぜ掛けてよいのか。 $600$ の約数は「$8$ の約数」$\times$「$3$ の約数」$\times$「$25$ の約数」の形にただ $1$ 通りに書ける(素因数分解の一意性)。たとえば約数 $60=4\times 3\times 5$ は、$8$ の約数 $4$、$3$ の約数 $3$、$25$ の約数 $5$ の組から作られ、他の組み合わせでは作れない。

だから、$3$ つの和を掛け合わせて展開すると、$24$ 個の項がちょうど $24$ 個の約数と $1$ 対 $1$ に対応する。

$$(1+2+4+8)(1+3)(1+5+25)=1\cdot 1\cdot 1+1\cdot 1\cdot 5+\cdots +8\cdot 3\cdot 25$$

$24$ 個の項 $=$ $24$ 個の約数。「掛けて展開する」ことが「全部の約数を作って足す」ことと同じだ。

この性質を数学では乗法性という。 「互いに素な部分に分けて、それぞれで計算し、最後に掛ける」のは、整数の問題でよく使う方法である。約数の個数も同じ($4\times 2\times 3=24$)。

検算の手。 約数をペアで数えてみよう。掛けて $600$ になる組は $(1,600),(2,300),(3,200),(4,150),(5,120),(6,100),(8,75),(10,60),(12,50),(15,40),(20,30),(24,25)$ で、ちょうど $12$ 組ある。$1$ 組に $2$ 個ずつだから $24$ 個。公式の答えと一致した。

約数の総和 $1860$ は元の数 $600$ の $3$ 倍以上もある。約数がたくさんある数($600$ は $24$ 個も持つ)では、こういうことが起こる。約数の「豊かさ」を測る量として、整数論では σ(シグマ)という記号で書かれ、完全数や友愛数といった話題で使われる。

方針

解答

⓪ 発想(どう考え始めるか) 最大公約数(gcd)と最小公倍数(lcm)は、素因数分解して指数を見比べるとすぐに出る。

$$48=2^4\times 3,60=2^2\times 3\times 5$$

• 最大公約数: 両方が持っている素因数を、少ないほうの個数だけとる
• 最小公倍数: どちらかが持っている素因数を、多いほうの個数だけとる

$2$ は $4$ 個と $2$ 個 → gcd では $2^2$、lcm では $2^4$。$3$ は $1$ 個ずつ → どちらも $3^1$。$5$ は $60$ だけ → gcd には入らない、lcm には $5^1$。

$$\gcd =2^2\times 3=12,\mathrm{lcm}=2^4\times 3\times 5=240$$

「共通のものだけ・少ないほう」が gcd、「全部・多いほう」が lcm。 迷ったら指数を並べて書く。

$48=2^4\times 3$、$60=2^2\times 3\times 5$ と素因数分解する。

(1) 各素因数の指数を見比べる。

最大公約数(共通して持てる分=指数の小さいほう):$2$ は $2$ 個、$3$ は $1$ 個、$5$ は片方にしかないので $0$ 個。よって

$$2^2\times 3=12$$

最小公倍数(どちらも割り切る最小の数=指数の大きいほう):$2$ は $4$ 個、$3$ は $1$ 個、$5$ は $1$ 個。よって

$$2^4\times 3\times 5=240$$

(2)

$$12\times 240=2880,48\times 60=2880$$

まとめ:確かに等しい。これは偶然ではない。どの素因数も『小さいほうの指数 $+$ 大きいほうの指数 $=$ 元の2数の指数の和』になるから、$(\text{最大公約数})\times (\text{最小公倍数})=(2\text{数の積})$ はいつでも成り立つ。

発展。 最小公倍数は身のまわりで意外なほど活躍する。

歯車。 歯数 $48$ と $60$ の $2$ つの歯車がかみ合って回るとき、最初と同じ歯どうしが再び出会うのは、$\mathrm{lcm}(48,60)=240$ 個の歯が噛み合ったとき。小さい歯車は $240÷48=5$ 回転、大きいほうは $240÷60=4$ 回転している。

うるう年・カレンダー。 「同じ曜日・同じ日付」が戻ってくる周期も、$7$ と $365$(や $366$)の絡んだ公倍数の問題だ。

セミ。 北アメリカには $13$ 年ゼミと $17$ 年ゼミがいる。どちらも素数年なのは偶然だろうか。もし周期が $12$ 年なら、$2,3,4,6$ 年周期の天敵と頻繁に鉢合わせしてしまう。素数なら、天敵との出会いの周期(最小公倍数)が最大になる。$13$ と $17$ が同時に地上に出るのは、$\mathrm{lcm}(13,17)=221$ 年に $1$ 度だけだ。

進化が最小公倍数を計算していたという説である(異説もある)。

歯車の噛み合い、暦の巡り、生物の生存戦略など、「いつ再び出会うか」という問いがあるところには、必ず最小公倍数が現れる。最小公倍数を使えば、こうした周期の問題を式で扱える。

別解

(2)で確かめた $\gcd \times \mathrm{lcm}=48\times 60$ という関係は、偶然ではない。 なぜ必ず成り立つのかを見抜けば、この式は「暗記する公式」から「当たり前の事実」に変わる。

指数を表にして並べる。

ここで、いちばん右の $2$ 列に注目してほしい。

$2$ の行: gcd の指数 $2$ と lcm の指数 $4$。足すと $2+4=6$。 一方、元の $2$ つの数の指数は $4$ と $2$。足すと $4+2=6$。

同じだ。

$5$ の行: gcd が $0$、lcm が $1$ → 和は $1$。元は $0$ と $1$ → 和は $1$。やはり同じ。

当たり前である。 $2$ つの数 $a$、$b$ について、小さいほう(min)と大きいほう(max)を足せば、必ず元の $2$ つの和になるからだ。

$$\min (a,b)+\max (a,b)=a+b$$

($a\leqq b$ なら $\min =a$、$\max =b$ で、和は当然 $a+b$ になる。)

だから、すべての素因数について指数の和が保たれる。 指数の和が同じということは、掛け算の結果が同じということ。

$$\gcd (48,60)\times \mathrm{lcm}(48,60)=48\times 60$$

$\min$ と $\max$ を足せば元に戻る、という事実が、この公式の根拠だった。実用上、この関係はとても役に立つ。

$$\mathrm{lcm}(a,b)=\frac{a\times b}{\gcd (a,b)}$$

lcm はgcd さえ分かれば割り算 $1$ 回で出る。 そして gcd は素因数分解しなくても互除法で高速に求められる(後で学ぶ)。

大きな数ほど、この方法が役に立つ。 たとえば $\mathrm{lcm}(319,377)$ を素因数分解で求めるのは骨が折れるが、互除法で $\gcd =29$ と分かれば

$$\mathrm{lcm}=\frac{319\times 377}{29}=\frac{120263}{29}=4147$$

素因数分解を一切せずに、最小公倍数が出た。 「gcd を先に、lcm は割り算で」求めるのが実戦の手順である。

なお、$3$ つ以上の数ではこの公式は成り立たない($\gcd (a,b,c)\times \mathrm{lcm}(a,b,c)\ne abc$ が普通)。$2$ 数限定の関係だと覚えておきたい。

方針

解答

⓪ 発想(どう考え始めるか) 「これ以上約分できない」とは、分子と分母の最大公約数が $1$($=$ 互いに素)ということ。

だから最大公約数でまとめて割るのが最短ルートだ。

$$84=2^2\times 3\times 7,126=2\times 3^2\times 7$$

共通するのは $2$($1$ 個ずつ)、$3$($1$ 個ずつ)、$7$($1$ 個ずつ)。

$$\gcd (84,126)=2\times 3\times 7=42$$

$$\frac{84}{126}=\frac{84÷42}{126÷42}=\frac{2}{3}$$

$2$ で割って $\frac{42}{63}$、$3$ で割って $\frac{14}{21}$、$7$ で割って $\frac{2}{3}$ と少しずつ進めてもよいが、途中で「もう終わり」と勘違いしやすい。最大公約数で $1$ 回で割り切るほうが安全である。分母と分子の最大公約数で割ると、一度で既約分数になる。

$84=2^2\times 3\times 7$、$126=2\times 3^2\times 7$。共通の素因数は $2$ が $1$ 個、$3$ が $1$ 個、$7$ が $1$ 個だから、最大公約数は

$$2\times 3\times 7=42$$

分母・分子を $42$ で割って

$$\frac{84}{126}=\frac{84÷42}{126÷42}=\frac{2}{3}$$

$2$ と $3$ には $1$ 以外の共通の約数がない(互いに素)ので、これ以上は約分できない。これが既約分数だ。

発展。 「互いに素」という関係は、整数論のいたるところで使われる。

$1$ から $n$ までのうち、$n$ と互いに素な数の個数を $\phi (n)$(オイラー関数)と書く。たとえば $\phi (12)=4$($1,5,7,11$ の $4$ 個)。この関数は現代の暗号(RSA暗号)で使われている。インターネットの買い物で使われる暗号にも、「互いに素」という考え方が使われている。

もう $1$ つ、関連する事実を紹介する。 $2$ つの自然数をランダムに選んだとき、それらが互いに素である確率はいくつだろうか。答えは

$$\frac{6}{{\pi }^2}\approx 0.608$$

$\pi$ が出てくる。 円周率が整数の話に現れる理由は、大学の解析学と整数論の両方にまたがる内容だ。

約分という小学校以来の作業から、$\pi$ が出てきた。 $\frac{84}{126}$ を $\frac{2}{3}$ に直す約分も、この確率の話とつながっている。

別解

素因数分解をせずに、互除法で最大公約数を求めるルートを見ておこう。大きな数になったとき、この差は大きくなる。互除法(割り算を繰り返す)。

$$126÷84=1\text{余り}42$$

$$84÷42=2\text{余り}0$$

余りが $0$ になった。そのときの「割る数」$42$ が最大公約数である。

$$\frac{84}{126}=\frac{2}{3}$$

素因数分解をまったくしていない。 割り算 $2$ 回で終わった。

なぜこれで gcd が出るのか。 使うのは次の事実だ。

$$126\text{と}84\text{の公約数}=84\text{と}42(\text{余り})\text{の公約数}$$

$126=84+42$ だから、$84$ と $42$ を割り切る数は $126$ も割り切る。逆も同じ。つまり「元の $2$ 数の公約数」と「割る数と余りの公約数」は、まったく同じ集合である。

だから数をどんどん小さくしながら gcd を保てる。大きい数の問題を、小さい数の問題にすり替えていく。これが互除法の仕組みだ。

どちらのルートを選ぶべきか。

• 小さい数($100$ 以下くらい)→ 素因数分解が直感的で速い
• 大きい数($3$ 桁以上、素因数が見えにくい)→ 互除法のほうがずっと速い

たとえば $\frac{319}{377}$ を約分せよ、と言われたら。素因数分解は苦しい($319=11\times 29$ に気づけるだろうか)。しかし互除法なら

$$377÷319=1\text{余り}58,319÷58=5\text{余り}29,58÷29=2\text{余り}0$$

$3$ 回の割り算で $\gcd =29$。約分すると $\frac{11}{13}$ だ。

素因数分解は「難しい」が、最大公約数は「易しい」。 この差は大きい。$2$ つの $300$ 桁の数の素因数分解には数万年かかるが、その最大公約数は $1$ 秒未満で求まる。

紀元前 $300$ 年ごろのユークリッドが書き残したこの手続きは、$2300$ 年後の今もコンピュータの中で毎秒動き続けている。知られている中で最も古く、今も使われているアルゴリズムである。

方針

解答

⓪ 発想(どう考え始めるか) 「$n$ はどんな整数でもよい」とある。無限にある整数を、どうやって全部調べるのかを考える。

答えは余りで仲間分けすること。$3$ で割った余りは $0$、$1$、$2$ の $3$ 種類しかない。だから整数は

$$n=3k,n=3k+1,n=3k+2(k\text{は整数})$$

の $3$ グループに完全に分かれる。無限個の整数が $3$ 通りにまとまった。

あとはこの $3$ 通りそれぞれについて $n^2$ を計算し、$3$ で割った余りを調べればよい。

$3$ 通りとも調べること。 $1$ つでも飛ばせば「すべての整数について」の証明にならない。余りによる分類は無限を有限にする技である。

整数 $n$ は $3$ で割った余りによって $3$ 種類に分けられる。$n=3k$、$n=3k+1$、$n=3k+2$($k$ は整数)のどれかだ。それぞれで $n^2$ を計算して、$3$ で割った余りを調べる。

$n=3k$ のとき:$n^2=9k^2=3\cdot 3k^2$。余りは $0$。$n=3k+1$ のとき:$n^2=9k^2+6k+1=3(3k^2+2k)+1$。余りは $1$。

$n=3k+2$ のとき:$n^2=9k^2+12k+4=3(3k^2+4k+1)+1$。余りは $1$。どの場合も余りは $0$ か $1$ で、$2$ にはならない。

$$n^2\text{ を }3\text{ で割った余りは }0\text{ または }1$$

まとめ:この『余りで分けて調べる』方法は整数の証明で役に立つ道具になる。たとえば『$3n^2-1$ は平方数にならない』も、この結果から言える(平方数の余りは $0,1$ なのに、$3n^2-1$ は余り $2$ だからだ)。

発展。 同じ発想を $\mathrm{mod}4$ でやってみよう。整数は $2k$ か $2k+1$ だから

$$(2k{)}^2=4k^2\equiv 0,(2k+1{)}^2=4k^2+4k+1\equiv 1(\mathrm{mod}4)$$

平方数を $4$ で割った余りは $0$ か $1$ だけ。ここから、たちどころに次が分かる。$2$ つの平方数の和 $x^2+y^2$ を $4$ で割った余りは

$$0+0=0,0+1=1,1+1=2$$

の $3$ 通りしかない。$3$ にはならない。

だから $x^2+y^2=3$、$x^2+y^2=7$、$x^2+y^2=4003$ には整数解がない($4003$ を $4$ で割ると $3$ 余る)。無限個の数を1回の計算で否定できた。

このように「どの数で割って見るか($\mathrm{mod}$ を何にするか)」を選ぶセンスが、整数問題の腕の見せどころだ。$\mathrm{mod}3$、$\mathrm{mod}4$、$\mathrm{mod}8$、$\mathrm{mod}9$ など、平方数、立方数、素数の性質に応じて、有効な法が変わる。

大学入試の整数問題で「解が存在しないことを示せ」と言われたら、まず適当な数で割ってみる。$9$ 割はこれで片がつく。余りで考えることは、不可能を証明するのに向いている。

別解

合同式という記号を使うと、この証明が数行で終わる。しかも、そこから応用が生まれる。

合同式の書き方。 $n$ を $3$ で割った余りが $r$ のとき

$$n\equiv r(\mathrm{mod}3)$$

と書く。「$\mathrm{mod}$」は「割った余りで見る」という意味だ。この記号の便利なところは、足し算・掛け算がそのままできることだ。

$$a\equiv b,c\equiv d⟹ac\equiv bd(\mathrm{mod}3)$$

だから、$n\equiv r$ なら $n^2\equiv r^2$ が言える。$3$ 通りの $r$ について $r^2$ を計算するだけでよい。

表 $1$ つで証明が終わった。 $n^2$ を $3$ で割った余りは $0$ か $1$ だけ。$2$ は決して出てこない。

$(3k+2{)}^2=9k^2+12k+4$ と展開する必要すらない($9k^2$ も $12k$ も $3$ の倍数なので消え、$4\equiv 1$ が残る。合同式を使えば、この計算を自動で済ませられる)。さて、この結論は何の役に立つのか。

「$3$ で割って $2$ 余る数は、決して平方数ではない」 ということが使える。たとえば、こう問われたとしよう。「$2024$ は平方数か?」

わざわざ平方根を計算しなくてよい。 $2024$ の各位の和は $2+0+2+4=8$ なので、$3$ で割った余りは $2$。

$$2024\equiv 2(\mathrm{mod}3)$$

平方数の余りは $0$ か $1$ しかない。だから $2024$ は平方数ではない。これで証明が終わる。(ちなみに $45^2=2025$ で、惜しくも $1$ 違いだった。)

この手口は「不可能の証明」でとても役に立つ。

• $x^2+y^2=3$ を満たす整数はあるか? → $\mathrm{mod}4$ で考えると存在しないと分かる
• ある方程式に整数解はあるか? → 適当な数で割った余りを見て、矛盾を探す

「実際に探して見つからない」ことと「存在しないと証明する」ことは、まったく違う。 前者は永遠に終わらないが、後者は余りの表 $1$ つで片づく。

余りの種類は少ない($3$ 通りだけ)。だからこそ、余りで矛盾を見つければ、無限にある整数の話に決着がつく。 これは整数論でよく使う方法である。

方針

解答

⓪ 発想(どう考え始めるか) 「必ず $\dots$ になる」を示せと言われたら、具体例をいくつ挙げても証明にならない。$1\times 2=2$、$2\times 3=6$、$3\times 4=12$ はすべて偶数だが、これは「たまたま調べた $3$ 個がそうだった」だけだ。

すべての整数 $n$ について言えなければならない。そこで偶奇で場合分けする。整数は必ず

$$n=2k(\text{偶数})\text{または}n=2k+1(\text{奇数})$$

のどちらかだ($k$ は整数)。この $2$ つで、すべての整数を尽くしている。

あとは、それぞれで $n(n+1)$ を計算し、$2\times (\text{整数})$ の形になることを見せる。

「$2\times$(整数)」と書けたら、それが偶数の定義そのもの。ここまで書き切って、はじめて証明になる。

連続する $2$ つの整数 $n$、$n+1$ のうち、必ず一方は偶数だ。それを $n$ の偶奇で分けて示す。$n$ が偶数のとき:$n=2k$($k$ は整数)とおけて

$$n(n+1)=2k(n+1)=2\times k(n+1)$$

となり、$2\times$(整数)なので偶数。$n$ が奇数のとき:$n+1$ が偶数になる。$n+1=2k$ とおけて

$$n(n+1)=n\times 2k=2\times kn$$

となり、やはり偶数。どちらの場合も $n(n+1)$ は $2$ の倍数である。$■$

(同じ考え方で、連続する $3$ つの整数の積は必ず $6$ の倍数になる。このうち1つは必ず偶数、1つは必ず $3$ の倍数だからだ。)

発展。 この問題から分かるのは、数学の証明における 「すべて」と「ある」の違いである。

• 「すべての $n$ で成り立つ」を示すには → 論証が要る。例をいくつ並べても足りない
• 「成り立たない $n$ がある」を示すには → 反例を $1$ つ挙げれば終わり

この非対称性をいつも意識したい。たとえば「$n^2+n+41$ は必ず素数である」という主張を考えよう。$n=0,1,2,\dots ,39$ まで試すと、$40$ 個すべてが素数になる(オイラーが見つけた有名な式だ)。

「$40$ 個も確かめたのだから正しいだろう」と思える。しかし $n=40$ で破綻する。

$$40^2+40+41=41\times 41$$

$41$ の倍数になってしまう。 $40$ 個の成功例は $1$ 個の反例の前に無力だった。

「たくさん確かめたから正しい」は、数学では通用しない。 逆に「$1$ つ反例を見つけたら、それで終わり」でもある。

$n(n+1)$ が偶数であることを、$100$ 個の例で確かめても証明にはならない。しかし $n=2k$ と $n=2k+1$ の $2$ 行を書けば、無限個すべてをまとめて証明できる。

論証を使えば、無限個の場合を有限の手順で示せる。

別解

「連続する $2$ 整数のうち、一方は必ず偶数」 という一言で証明を終わらせる、より直接的なルートを見る。そして、この事実の一般化を紹介する。別証明1: 偶数は交互に現れる。

整数を数直線に並べる。

$$\cdots ,\underset{\text{偶}}{\underbrace{-2}},\underset{\text{奇}}{\underbrace{-1}},\underset{\text{偶}}{\underbrace{0}},\underset{\text{奇}}{\underbrace{1}},\underset{\text{偶}}{\underbrace{2}},\underset{\text{奇}}{\underbrace{3}},\cdots$$

偶数と奇数は、必ず交互に並ぶ。 だから隣り合う $2$ つの整数 $n$、$n+1$ は、必ず一方が偶数で他方が奇数になる(両方とも奇数、ということはありえない)。

偶数を $1$ つでも含む積は、偶数である。よって $n(n+1)$ は偶数。証明終わり。

場合分けの計算をせずに、構造(偶奇の交替)を見て言い切る。これが「見通しのよい証明」だ。別証明2: 組合せの個数として見る。

$$\frac{n(n+1)}{2}={}_{n+1}{\mathrm{C}}_2$$

右辺は「$n+1$ 個から $2$ 個を選ぶ選び方の数」 なので、当然整数である(何かの個数なのだから、分数や小数であるはずがない)。左辺が整数ということは、$n(n+1)$ は $2$ で割り切れる。証明終わり。

「数え上げの個数だから整数」という論法は、整数論では有効な方法になる。計算をせず、意味に訴えて割り切れることを示すのだ。そして、これは一般化する。

$$\frac{n(n+1)(n+2)}{6}={}_{n+2}{\mathrm{C}}_3(\text{整数})$$

つまり連続する $3$ 整数の積は必ず $6$($=3!$)の倍数。一般に

$$\boxed{\text{連続する k 個の整数の積は、必ず }k!\text{の倍数}}$$

連続 $2$ 個なら $2!=2$ の倍数、連続 $3$ 個なら $6$ の倍数、連続 $4$ 個なら $24$ の倍数。

なぜか。 連続する $k$ 個の中には $2$ の倍数も、$3$ の倍数も、$\dots$、$k$ の倍数も、必ず含まれているからだ(もっと正確には、上の組合せの式で保証される)。

この一般化は入試の整数問題でよく使われる。「$n^3-n$ が $6$ の倍数であることを示せ」という問題なら、因数分解すれば

$$n^3-n=n(n-1)(n+1)=(n-1)n(n+1)$$

連続する $3$ 整数の積だ。だから $6$ の倍数。 場合分けも合同式も要らない。

問題を「連続整数の積」の形に持ち込めれば、解ける。 そのために因数分解する。この一手に気づけるかどうかが、整数問題の分かれ目である。

方針

解答

⓪ 発想(どう考え始めるか) $319$ と $377$ の最大公約数。素因数分解しようとしても、手が止まるはずだ($319$ を割り切る素数がすぐには見えない)。

こういうときのための道具がユークリッドの互除法である。手順は機械的だ。大きいほうを小さいほうで割り、余りを出す。次は「割る数」と「余り」で同じことを繰り返す。余りが $0$ になったら、そのときの割る数が答え。

$$377÷319=1\cdots \text{余り }58$$

$$319÷58=5\cdots \text{余り }29$$

$$58÷29=2\cdots \text{余り }0$$

余りが $0$ になった。そのとき割っていた数 $29$ が最大公約数。

最後の余り($0$)ではなく、その手前の「割る数」が答え。 ここを取り違えないこと。

互除法は『割って余りを出す』をくり返すだけだ。$377$ を $319$ で割ることから始める。

$$377=1\times 319+58$$

$$319=5\times 58+29$$

$$58=2\times 29+0$$

余りが $0$ になった。そのときの割る数 $29$ が最大公約数だ。

$$\gcd (319,377)=29$$

(なぜこれで求まるのか。『$377$ と $319$ の公約数』は『$319$ と余り $58$ の公約数』とぴったり同じだ。余りを取っても公約数は変わらない。だから数をどんどん小さくしていって、最後に残る数が最大公約数になる。素因数分解しにくい大きな数でも使えるのが強みだ。)

発展。 互除法には、逆に読むという使い方がある。計算の跡を逆走すると、次の形の式が作れるのだ。

$$319x+377y=29(\text{整数 }x,y)$$

実際、互除法の式を下から順に代入していくと

$$29=319-58\times 5=319-(377-319)\times 5=319\times 6-377\times 5$$

$x=6$、$y=-5$ が見つかった。 確かめると $319\times 6-377\times 5=1914-1885=29$。一般に、次の定理が成り立つ。

$$ax+by=\gcd (a,b)\text{を満たす整数 }x,y\text{ が必ず存在する}$$

これはとても役に立つ。 特に $a$ と $b$ が互いに素($\gcd =1$)なら

$$ax+by=1$$

を満たす整数が存在する。これが $1$ 次不定方程式が解ける理由であり(次の問題で使う)、暗号理論で「逆元を求める」操作の中身でもある。

互除法はgcd を求めるだけの道具ではなく、割り算の跡を逆にたどることで、方程式の解まで求められる。

$2300$ 年前のアルゴリズムが今も現役なのは、速いだけでなく、副産物として方程式の解まで得られるからだ。数学の道具はしばしば作った人の意図を超えて働く。

別解

互除法が本当に正しいのか、素因数分解で答え合わせをしよう。そして互除法を図形として見ると、この $2300$ 年前のアルゴリズムの仕組みがよく分かる。

答え合わせ: 素因数分解でも求めてみる。

$$319=11\times 29,377=13\times 29$$

共通の素因数は $29$ だけ($11$ と $13$ は互いに素)。

$$\gcd (319,377)=29$$

互除法の答えと一致した。

しかし、この分解を見つけるのは大変だったはずだ。$319$ を $2,3,5,7$ で割っても割り切れず、$11$ でようやく割れる。$377$ も $13$ まで試す必要がある。互除法なら、割り算 $3$ 回で終わった。

互除法を図形で見る。$377\times 319$ の長方形を、正方形のタイルで敷き詰めることを考えよう。できるだけ大きな正方形で、余りなく敷き詰めたい。

手順1: いちばん大きく取れるのは $319\times 319$ の正方形。$1$ 個切り取ると、$58\times 319$ の長方形が残る。

$$377=319\times 1+58$$

手順2: 残った長方形から、$58\times 58$ の正方形を切り取る。$5$ 個取れて、$29\times 58$ が残る。

$$319=58\times 5+29$$

手順3: $29\times 29$ の正方形がちょうど $2$ 個で、余りなく埋まった。

$$58=29\times 2+0$$

最後にぴったり埋まった正方形の $1$ 辺が $29$。これが最大公約数である。

互除法とは「長方形を、できるだけ大きな正方形で敷き詰める手続き」である。ユークリッドが『原論』でこれを幾何の言葉で書いたのは、偶然ではない。$2$ つの数の共通の「ものさし」を探す。それが最大公約数の意味である。

互除法の速さ。 この方法はとても速い。$2$ 数がどんなに大きくても、割り算の回数は桁数の $5$ 倍程度にしかならない(フィボナッチ数列を使って証明できる)。

$300$ 桁の数どうしでも、$1500$ 回程度の割り算で gcd が出る。計算機ならすぐに終わる。一方、同じ数を素因数分解しようとすると、非常に長い時間がかかる。

「割り算を繰り返す」という原始的な操作が、素因数分解という難問を迂回して、答えにたどり着く。 アルゴリズムの勝利である。

方針

解答

⓪ 発想(どう考え始めるか) $7x+3y=2$ を満たす整数の組は、$1$ つではなく無限にある。だから「すべて求めよ」と言われている。

手順は $2$ 段階だ。

第 $1$ 段: 解を $1$ つ、何らかの方法で見つける(特殊解)。 小さい数を代入して探せばよい。$x=-1$ とすると $-7+3y=2$ から $y=3$。

$$7(-1)+3(3)=-7+9=2$$

第 $2$ 段: そこから、他のすべての解を作る。 見つけた解からどうずらせば、また解になるかを考える。$x$ を $3$ 増やすと左辺は $7\times 3=21$ 増える。$y$ を $7$ 減らすと $3\times 7=21$ 減る。プラマイちょうど $0$ になる。だからまた解になる。

$x$ は $y$ の係数($3$)だけ、$y$ は $x$ の係数($7$)だけずらす。 ここを取り違えやすい。

まず1組見つける。 小さい数を試すと、$x=-1$、$y=3$ が当てはまる($7\times (-1)+3\times 3=-7+9=2$)。

全部の解を表す。 見つけた解を基準にする。$7x+3y=2$ から、$7\times (-1)+3\times 3=2$ を辺々引くと

$$7(x+1)+3(y-3)=0\text{すなわち}7(x+1)=-3(y-3)$$

左辺は $7$ の倍数だから、右辺 $-3(y-3)$ も $7$ の倍数。$3$ と $7$ は互いに素なので、$y-3$ のほうが $7$ の倍数でなければならない。$y-3=-7t$($t$ は整数)とおくと $y=3-7t$。これを戻して $7(x+1)=-3\times (-7t)=21t$、つまり $x+1=3t$、$x=-1+3t$。

$$x=-1+3t,y=3-7t(t\text{ は整数})$$

($x$ の係数 $7$ と $y$ の係数 $3$ が、そっくり入れかわって『ずれ幅』になっているのがおもしろい。$t=0$ で、最初に見つけた解に戻る。)

発展。 $7x+3y=2$ の解を座標平面に打つと、直線 $7x+3y=2$ の上に、等間隔に並ぶ格子点になる。

$$\dots ,(-4,10),(-1,3),(2,-4),(5,-11),\dots$$

$x$ 方向に $3$、$y$ 方向に $-7$ ずつ、規則正しく並んでいる。 「不定方程式を解く」とは直線上の格子点をすべて見つけることである。そして、この構造は現実の問題を解く。

「$7$ 円切手と $3$ 円切手を組み合わせて、ちょうど $50$ 円ぶんにしたい。何枚ずつ買えばよいか」

$$7x+3y=50(x\geqq 0,y\geqq 0)$$

今度は 「非負整数解」だけが意味を持つ。無限にある解のうち、$x\geqq 0$ かつ $y\geqq 0$ のものだけを拾う。範囲で絞る。

さらに次の問いも考えられる。「$7$ 円と $3$ 円の切手で、どうやっても作れない金額は何か?」$1,2,4,5,8,11$ を調べると、$11$ 円が最大の作れない金額で、$12$ 円以上はすべて作れる。この最大値には公式があって

$$ab-a-b=7\times 3-7-3=11$$

フロベニウスの硬貨問題と呼ばれる有名な結果だ($a$、$b$ が互いに素なときに成り立つ)。

「解が無限にある」不定方程式に、「範囲」という条件を足すと、有限個の解を調べる問題に変わる。 入試の整数問題はたいていこの形をしている。

別解

特殊解を「勘で探す」のが不安なら、合同式で機械的に絞り込める。 係数が大きい問題では、こちらのほうが確実だ。両辺を $3$ で割った余りで見る($\mathrm{mod}3$)。

$$7x+3y=2$$

$3y$ は $3$ の倍数なので、$\mathrm{mod}3$ では消える。$7\equiv 1(\mathrm{mod}3)$ だから

$$7x\equiv 2(\mathrm{mod}3)⟹x\equiv 2(\mathrm{mod}3)$$

「$x$ を $3$ で割ると $2$ 余る」と分かった。 つまり

$$x=3t+2(t\text{は整数})$$

$y$ は元の式に代入して出す。

$$7(3t+2)+3y=2⟹21t+14+3y=2⟹3y=-21t-12$$

$$y=-7t-4$$

答え: $x=3t+2$、$y=-7t-4$($t$ は整数)。

あれ、本解と形が違う。 本解は $x=-1+3t$、$y=3-7t$ だった。どちらが正しいのか?

どちらも正しい。同じ解の集合を、違う「番地」で書いているだけである。確かめよう。本解の $t$ に $t+1$ を代入すると

$$x=-1+3(t+1)=3t+2$$ $$y=3-7(t+1)=-7t-4$$

ぴったり一致した。 $t$ のふり方(どの解を「$t=0$」と呼ぶか)が $1$ つずれているだけだ。実際に解をいくつか並べてみれば、同じ集合だと分かる。

$$\dots ,(-4,10),(-1,3),(2,-4),(5,-11),\dots$$

どちらの式もこの同じ列を生み出す。 出発点(特殊解)をどこに取るかで、式の見た目は変わる。しかし解の集合は $1$ つである。

だから、答えが教科書と違って見えても、あわてないこと。 $t$ をずらして一致するか確かめればよい。

合同式ルートの利点。 特殊解を勘で探さなくてよいので、係数が大きいときに強い。たとえば $37x+23y=5$ のような問題では、代入で解を探すのは苦しいが、$\mathrm{mod}23$ で $x$ を絞り込めば機械的に進める(もっと大きな係数なら、互除法を逆にたどる方法もある)。

この方程式が解けるのは、$7$ と $3$ が互いに素だからである。もし $6x+3y=2$ なら、左辺は必ず $3$ の倍数なのに右辺は $2$ なので、解は $1$ つも存在しない。

$$ax+by=c\text{が整数解を持つ}⟺\gcd (a,b)\text{が}c\text{を割り切る}$$

解く前に、まず解があるかを確かめる。これが不定方程式の作法である。

方針

解答

⓪ 発想(どう考え始めるか) $\frac{n+5}{n+1}$ に $n=1,2,3,\dots$ を代入して探し続けるのでは、どこまで探せば終わりなのか分からない。

そこで分子を、分母で割ってしまう。

$$\frac{n+5}{n+1}=\frac{(n+1)+4}{n+1}=1+\frac{4}{n+1}$$

この変形がすべてだ。 前半の $1$ は必ず整数。だから

$$\frac{n+5}{n+1}\text{が整数}⟺\frac{4}{n+1}\text{が整数}⟺n+1\text{が 4 の約数}$$

「無限に探す問題」が「$4$ の約数を挙げる問題」になった。 $4$ の約数は $1,2,4$ の $3$ つだけで、有限個である。$n$ は自然数なので $n+1\geqq 2$。$n+1=1$ は使えない(それは $n=0$ で自然数でない)。

分子を分母に合わせて分ける。$n+5=(n+1)+4$ なので

$$\frac{n+5}{n+1}=\frac{(n+1)+4}{n+1}=1+\frac{4}{n+1}$$

$1$ は整数だから、全体が整数になるのは $\frac{4}{n+1}$ が整数のとき。つまり $n+1$ が $4$ の約数であればよい。$4$ の正の約数は $1,2,4$。$n$ は自然数($n\ge 1$)なので $n+1\ge 2$、よって $n+1=2$ または $4$。

• $n+1=2$ → $n=1$(このとき $\frac{6}{2}=3$ で整数)
• $n+1=4$ → $n=3$(このとき $\frac{8}{4}=2$ で整数)

$$n=1,3$$

まとめ:『分数を整数部分と余りに分ける』→『分母が余りの約数』という流れが、この型のコツだ。

発展。 「$n$ が自然数」という条件が、この問題では欠かせなかった。もし「$n$ は整数」だったら、答えは増える。

$n+1$ は $4$ の約数だから、負の約数も許される。

$$n+1=\pm 1,\pm 2,\pm 4⟹n=0,-2,1,-3,3,-5$$

($n=-1$ は分母が $0$ になるので除く。)$6$ 個に増えた。

「自然数」「整数」「正の整数」のどれかという一語で、答えの個数が変わる。 問題文の条件を読み飛ばすと、正解が不正解になる。整数問題では次の $3$ つを毎回確認する習慣をつけたい。

• 範囲: 自然数か、整数か、正か、$0$ を含むか
• 分母が $0$ にならないか: 除外すべき値はないか
• 符号: 負の約数を考えるべき状況か

「解を全部求めよ」と言われたら、「全部」の意味を、問題文で定義された範囲で確定させる。 数学の答案は条件の読み取りから始まっている。

別解

なぜ「有限個で終わる」と言い切れるのか。 グラフの目で見ると、その理由が視覚的に分かる。ついでに、この問題の型が入試でどう形を変えて出るかも見ておこう。

グラフで見る。

$$y=1+\frac{4}{n+1}$$

$n$ が大きくなると、$\frac{4}{n+1}$ はどんどん小さくなる。

$n\geqq 4$ になると、値は $1$ と $2$ のあいだに閉じ込められる。

$$1<\frac{n+5}{n+1}<2(n\geqq 4)$$

$1$ と $2$ のあいだに整数はない。 だから $n\geqq 4$ では決して整数にならない。探すのは $n=1,2,3$ の $3$ つだけでよい。これで有限個に絞れた。

実際に代入すると $n=1$ で $3$、$n=2$ で $\frac{7}{3}$(整数でない)、$n=3$ で $2$。

$$n=1,3$$

約数ルートと同じ答え。

この「はさみうちで有限に絞る」発想は、整数問題の基本だ。 整数にはすき間がある(隣り合う整数のあいだに他の整数はいない)。だから「値を $1$ と $2$ のあいだに閉じ込める」ことが、そのまま「解なし」の証明になる。実数では通用しない、整数ならではの論法である。

別の角度: 最大公約数から見る。$\frac{n+5}{n+1}$ が整数ということは、$n+1$ が $n+5$ を割り切るということ。

$$(n+5)-(n+1)=4$$

$n+1$ が $n+5$ と $n+1$ の両方を割り切るなら、その差 $4$ も割り切る。 これは互除法と同じ理屈だ($\gcd (n+5,n+1)=\gcd (4,n+1)$)。だから $n+1$ は $4$ の約数だ。$1$ 行で本解の結論に到達した。

「差をとる」という一手は、整数問題でとてもよく使う。$\frac{2n+7}{n+2}$ なら、分子から分母の $2$ 倍を引いて $3$ が残るので、$n+2$ は $3$ の約数。同じ手がそのまま通じる。

まとめると、この型には $3$ つの解き方がある。

• 分子を分母で割る(整数部分 $+$ 余りの分数)
• 差をとる(割り切るなら差も割り切る)
• はさみうち($1$ と $2$ のあいだに整数はない)

どれか $1$ つでも見えれば、無限の探索が有限の確認に変わる。

方針

解答

⓪ 発想(どう考え始めるか) $n$ 進法とは「$n$ 個たまったら、$1$ つ上の位に繰り上がる」という数の書き方だ。ふだん使う $10$ 進法は「$10$ たまったら繰り上がる」。

位の重みが $n$ のべき乗になる。

• $2$ 進法の位: $\dots ,32,16,8,4,2,1$(右から $2^0,2^1,2^2,\dots$)
• $5$ 進法の位: $\dots ,125,25,5,1$

(1) $n$ 進法 → $10$ 進法: 各桁に重みを掛けて足すだけ。

(2)(3) $10$ 進法 → $n$ 進法: $n$ で割り続けて、余りを下から並べる。

「下から」がすべて。 最初に出た余りが一の位、最後に出た余りが最上位。上から並べると逆さまの数になってしまう。

(1) $2$ 進法の各位の重みは右から $1,2,4,8,16,32,\dots$。$110101_{(2)}$ は右から $1,0,1,0,1,1$ なので

$$1\times 32+1\times 16+0\times 8+1\times 4+0\times 2+1\times 1=32+16+4+1=53$$

(2) $10$ 進法 → $2$ 進法は『$2$ で割った余りを下から並べる』。$45÷2=22$ 余り $1$、$22÷2=11$ 余り $0$、$11÷2=5$ 余り $1$、$5÷2=2$ 余り $1$、$2÷2=1$ 余り $0$、$1÷2=0$ 余り $1$。余りを最後から順に並べて

$$45=101101_{(2)}$$

(3) 同じように $5$ で割っていく。$45÷5=9$ 余り $0$、$9÷5=1$ 余り $4$、$1÷5=0$ 余り $1$。余りを最後から並べて

$$45=140_{(5)}$$

(検算:$1\times 25+4\times 5+0=45$。位の重みをかけて足すと元に戻る。)

発展。 $2$ 進法の $101101$ は $6$ 桁、$10$ 進法の $45$ は $2$ 桁。同じ数なのに、桁数がまるで違う。

一般に、$n$ 進法で $N$ を表すのに必要な桁数は、およそ ${\log }_{n}N$ 桁。底が小さいほど、桁は長くなる。 だから $2$ 進法の数はやたらと長い。

そこでコンピュータでは、$16$ 進法がよく使われる。$0$〜$9$ の後に $\mathrm{A}$〜$\mathrm{F}$ を使って $16$ 個の数字を表す記法だ。$16=2^4$ なので、$2$ 進法の $4$ 桁が $16$ 進法の $1$ 桁にぴったり対応する。

$$101101_{(2)}=\underset{2}{\underbrace{10}}\underset{\mathrm{D}}{\underbrace{1101}}\to 2{\mathrm{D}}_{(16)}$$

($2\times 16+13=45$)ウェブページの色指定 #FF0000(赤)を見たことがあるだろう。あれは $16$ 進法で $2$ 桁ずつ、赤・緑・青の強さ($0$〜$255$)を書いている。$\mathrm{FF}=15\times 16+15=255$ で、これが最大値だ。

画面の色も、ファイルの中身も、この $16$ 進法で書かれている。 $n$ 進法は教科書の中の抽象的な話ではなく、目の前の画面を作っている技術そのものである。

位取り記数法という発明($0$ を含む)がなければ、こうした技術は成立しなかった。数を「書く」方法が数を「使う」力を決める。記数法の歴史からそれが分かる。

別解

割り算を使わずに、「重りで天秤をつり合わせる」ように変換する方法がある。$2$ 進法では、こちらのほうが速くて間違えにくい。

(2) $45$ を $2$ 進法に、重み分解で。

$2$ 進法の位の重みは $1,2,4,8,16,32,64,\dots$。$45$ を超えない最大の重みから、貪欲に取っていく。

• $45$ から $32$ を引く → 残り $13$
• $13$ から $8$ を引く → 残り $5$
• $5$ から $4$ を引く → 残り $1$
• $1$ から $1$ を引く → 残り $0$

$$45=32+8+4+1$$

使った重みに $1$、使わなかった重みに $0$ を書く。

$$45=101101_{(2)}$$

割り算ゼロで変換できた。$2$ 進法の数字は $0$ か $1$ しかないので、「使うか使わないか」の $2$ 択にすぎない。天秤に $1,2,4,8,16,32$ グラムの分銅を載せて、$45$ グラムをつり合わせる。それが $2$ 進法である。

(3) $5$ 進法も同じ発想。 重みは $1,5,25,125,\dots$。ただし各桁は $0$〜$4$ まで使える。

• $45$ に $25$ はいくつ入るか → $1$ 個($25\times 1=25$)、残り $20$
• $20$ に $5$ はいくつ入るか → $4$ 個($5\times 4=20$)、残り $0$
• $1$ の位 → $0$

$$45=1\times 25+4\times 5+0\times 1=140_{(5)}$$

検算(逆変換)を必ずやる。 $1\times 25+4\times 5+0=25+20=45$。

$n$ 進法は「両替」と同じ考え方である。 $45$ 円を、$25$ 円玉 $1$ 枚・$5$ 円玉 $4$ 枚・$1$ 円玉 $0$ 枚で払うことが、$140_{(5)}$ の意味だ。同じ金額を、違う硬貨の組で表しているだけで、数そのものは何も変わっていない。

なぜ $2$ 進法がこれほど広く使われているのか。 コンピュータの回路は「電流が流れる($1$)/流れない($0$)」の $2$ 状態しか持てない。だから $2$ 進法が使われる。$10$ 段階の電圧を正確に区別するのは難しいが、オンとオフなら、ノイズがあっても間違えない。

「表現の仕方」が変わっても、数そのものは変わらない。 $45$ も $101101_{(2)}$ も $140_{(5)}$ も、まったく同じ量である。この視点が記数法を理解するうえで大切だ。