整数の性質 ★★ 標準の問題 全12問

方針

解答

⓪ 発想(どう考え始めるか) $6$ の倍数を直接判定する道具はない。でも $6=2\times 3$ で、$2$ と $3$ は互いに素だ。

だから「$2$ の倍数 かつ $3$ の倍数」に分解する。それぞれには判定法がある。$2$ の条件は一の位で決まり、今回は末尾 $6$ で自動的に合格。残るは $3$ の条件、つまり各位の和 $4+\square +6=10+\square$ が $3$ の倍数になる $\square$ を探すだけだ。

$6=2\times 3$ で、$2$ と $3$ は互いに素だから、$6$ の倍数とは『$2$ の倍数 かつ $3$ の倍数』のことだ。両方の条件を課す。

$2$ の倍数の条件:一の位が偶数。$\overline{4\square 6}$ の一の位は $6$ で偶数なので、$\square$ が何であってもこの条件は満たされる。

$3$ の倍数の条件:各位の和 $4+\square +6=10+\square$ が $3$ の倍数。$\square$ は $0$〜$9$ なので $10+\square$ は $10$〜$19$、この中の $3$ の倍数は $12,15,18$。よって $10+\square =12,15,18$、つまり

$$\square =2,5,8$$

発展。 「互いに素な2つに分解して別々に判定」は、$12=3\times 4$、$18=2\times 9$ など合成数の判定すべてに通じる設計だ。分解の相手が互いに素であることが条件で、$12=2\times 6$ のような分解では判定できない($2$ の倍数かつ $6$ の倍数でも $12$ の倍数とは限らない)。

各位の和で $3$ の倍数が判定できる理由は、$10\equiv 1$(mod $3$)にある。合同式を学ぶと、$9$ や $11$ の判定法まで同じ原理で作れる。

別解

候補が10個しかないので、「6の倍数の並び方」から見抜く道もある。$4\square 6$ の形の数は $406,416,426,\dots ,496$ の10個。この中の6の倍数を探すと $426,456,486$ で、ちょうど $30$ ずつ並んでいる。

これは偶然ではない。末尾が $6$ のまま次の6の倍数に進むには、$6$ の倍数かつ $10$ の倍数、つまり $30$ の倍数だけ足すしかないからだ。だから1つ見つければ($426=6\times 71$)、あとは $30$ 間隔で機械的に拾える。$\square =2,5,8$。

判定法ルートの「$10+\square$ が3の倍数 → $\square =2,5,8$(3間隔)」と、数直線上の「30間隔」が同じことの2つの表し方になっている。

方針

解答

⓪ 発想(どう考え始めるか) 「約数の個数 =(各指数 $+1$)の積」を、今回は逆向きに使う。

個数 $15$ を「(指数 $+1$)の積」に分解する。$15=15$ と $15=3\times 5$ の2通りだ。ここから指数の組($p^{14}$ 型と $p^2{q}^4$ 型)が決まる。

最小の数を作る仕上げは「大きい指数ほど小さい素数に割り当てる」。候補どうしを比べて最小を選ぶ。

約数の個数は『(各指数 $+1$)をかけたもの』。だから $15$ を『(指数 $+1$)の積』に分ける。$15=15$ または $15=3\times 5$。

$15=15$ の場合:指数 $+1=15$、つまり指数 $14$ の素数 $1$ つ。最小は $2^{14}$ で、これはとても大きい。

$15=3\times 5$ の場合:指数が $2$ と $4$ の素因数 $2$ つ。数を小さくするには、大きい指数 $4$ を小さい素数 $2$ に、指数 $2$ を次の素数 $3$ に割り当てる。

$$2^4\times 3^2=16\times 9=144$$

($2^2\times 3^4=4\times 81=324$ よりこちらが小さい。『大きい指数ほど小さい素数へ』が最小化のコツだ。)$2^{14}$ は $144$ よりはるかに大きいので、答えは

$$144$$

発展。 「約数の個数が奇数 ⟺ 平方数」には有名な応用がある。100枚のロッカーの開閉問題(1番から100番の人が自分の倍数番のロッカーを反転していくと、最後に開いているのは平方数番だけ)は、この事実の言い換えだ。

「個数ちょうど $k$ 個の最小数」は、$k$ の分解が増えるほど候補の比較が本格化する($k=12$ なら分解が4通り)。「大きい指数を小さい素数へ」の原理だけでは足りず、実際に数を比べる検分が最後に必要になる。

別解

計算の前に、答えがどんな数かを1つ予想できる。約数の個数 $15$ は奇数。実は、約数の個数が奇数になる数は平方数だけだ。

理由はペアの構造にある。約数は $d$ と $\frac{n}{d}$ のペアで現れるから、ふつうは偶数個。ペアが崩れるのは $d=\frac{n}{d}$、つまり $n=d^2$ となる、組の相手が自分自身になる約数があるときだけ。それが平方数だ。

だから答えは平方数のはず。実際、候補の $2^{14}=128^2$、$2^4\times 3^2=144=12^2$、$2^2\times 3^4=324=18^2$ はすべて平方数で、最小は $144$。「個数が奇数 ⟺ 平方数」は、それ自体が頻出の知識でもある。答えの形を先に知ってから計算に入ると、指数の割り当てミスにも気づきやすい。

方針

解答

⓪ 発想(どう考え始めるか) 最大公約数が $6$ という情報は、2数の「形」を表している。2数は $6a$、$6b$($a$、$b$ は互いに素)と書ける。

すると最小公倍数は $6ab$。これが $180$ だから $ab=30$。あとは、積が $30$ になる互いに素な組 $(a,b)$ を探すだけだ。「互いに素」の条件を忘れずに、順序を決めて($a\le b$)数えれば重複しない。

最大公約数が $6$ なので、$2$ 数は $6a$、$6b$ とおける。ここで $a$ と $b$ は互いに素($1$ 以外の共通約数を持たない)。もし共通約数があれば、最大公約数が $6$ より大きくなってしまうからだ。

このとき、最小公倍数は $6ab$ になる。条件より

$$6ab=180\text{よって}ab=30$$

$a\le b$、$a$ と $b$ は互いに素、$ab=30$ を満たす組を探す。$30$ を $2$ つの積に分けると $(1,30),(2,15),(3,10),(5,6)$ で、どれも互いに素だ。それぞれを $6$ 倍して

$$(6,180),(12,90),(18,60),(30,36)$$

(注意:$a$ と $b$ が互いに素であることが必要。$ab=30$ でも共通因数があれば最大公約数が $6$ からずれる。今回の $4$ 組はすべて互いに素なので、これで尽くされている。)

発展。 積の保存則 $\gcd \times \mathrm{lcm}=mn$ は、素因数の指数で見ると「min + max = 足し算」という当たり前の事実になる。各素数の指数について、gcd は小さい方、lcm は大きい方を取るからだ。

ただしこの保存則は2数限定で、3数では崩れる。指数の min と max だけでは真ん中の情報が消えるからだ。便利な公式ほど、適用範囲の境界を知っておく価値がある。

別解

検算の道具として、「積の保存則」を持っておくと強い。2つの自然数について、いつでも

$$(\text{最大公約数})\times (\text{最小公倍数})=(\text{2数の積})$$

が成り立つ。今回なら2数の積は必ず $6\times 180=1080$ になるはずだ。答えの4組を検分すると、$6\times 180=1080$、$12\times 90=1080$、$18\times 60=1080$、$30\times 36=1080$。すべて合格で、安心して提出できる。

この保存則が成り立つ理由も、$6a\times 6b=6\times 6ab=(\text{gcd})\times (\text{lcm})$ と、本解の形からすぐ出る。逆に、積 $1080$ を先に出して「積が1080で最大公約数が6の組」を探す攻め方もできる。

方針

解答

⓪ 発想(どう考え始めるか) 「互いに素」とは、$1$ 以外に共通の約数がないこと。示したいのは「無い」ことだ。

無いことの証明は、あると仮定して調べるのが基本になる。共通の約数を $d$ とおく。$d$ は $n$ も $n+1$ も割り切る。割り切るなら、その差 $(n+1)-n=1$ も割り切るはずだ。$1$ を割り切る正の整数は $1$ だけ。だから $d=1$ しかない。「差も割り切る」がこの問題の決め手である。

$n$ と $n+1$ の正の公約数を $d$ とする。$d$ は $n$ を割り切り、$n+1$ も割り切る。すると、その差も $d$ で割り切れる。

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

つまり $d$ は $1$ を割り切る。$1$ を割り切る正の整数は $1$ だけだから、$d=1$。よって $n$ と $n+1$ の公約数は $1$ しかなく、互いに素である。$■$

(決め手は『$2$ 数を割り切る数は、その差も割り切る』という性質。差が $1$ になったことで、公約数が $1$ に追い込まれた。連続整数が互いに素なのは、この『差 $1$』があるからだ。)

発展。 「差を取って公約数の候補を絞る」技は広く使える。たとえば $n+2$ と $2n+7$ の公約数は、$2(n+2)$ との差 $3$ の約数に限られる、という具合だ(分数が整数になる条件の問題で、この形がよく使われる)。

連続整数が互いに素である事実は、「連続する2整数の積は必ずどちらか一方の素因数しか持たない」など、整数の証明問題の部品として頻繁に引用される。1行で示せるようにしておきたい。

別解

互除法を学んだ目で見ると、この証明は1行になる。互除法の原理は「$\gcd (a,b)=\gcd (b,r)$($r$ は $a$ を $b$ で割った余り)」だった。$n+1$ を $n$ で割ると、商 $1$・余り $1$。だから

$$\gcd (n+1,n)=\gcd (n,1)=1$$

割り算1回で、最大公約数が $1$ と確定した。本解の「差も割り切る」は、実はこの互除法の1ステップ(余り $1$ に落ちる)を素朴な言葉で言ったものだ。連続する2整数は、いつでも互除法がすぐに終わる、共通の約数をもたない組である。

方針

解答

⓪ 発想(どう考え始めるか) 「$n^2$ の余り」を全部の $n$ で調べることはできない。そこで整数を有限のグループに分ける。

$4$ で割った余りが知りたいのだから、いちばん粗い分類から試す。偶数($n=2k$)と奇数($n=2k+1$)の2分類だ。

それぞれ2乗して $4$ で割れば、余りは $0$ と $1$ しか出ないと分かる。「余りが限られる」と分かれば、逆向きに「余り $3$ の数は平方数でない」という不可能の証明に使える。

$n$ を偶数・奇数で分ける。$n$ が偶数($n=2k$)のとき:$n^2=4k^2$。余りは $0$。$n$ が奇数($n=2k+1$)のとき:$n^2=4k^2+4k+1=4(k^2+k)+1$。余りは $1$。

よって、平方数を $4$ で割った余りは $0$ か $1$ のどちらかで、$2$ や $3$ にはならない。

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

応用:$4$ で割ると $3$ 余る整数を考える。もしそれが平方数なら、余りは $0$ か $1$ のはずなのに、余りが $3$ で矛盾する。だから『$4$ で割って $3$ 余る数』は平方数ではない($7,11,15,\dots$ はどれも平方数でない)。

(余りの性質は『できないこと(平方数でない)』を示すのに強い。)

発展。 「平方数の余りは限られる」は、不可能の証明でよく使う道具だ。$3$ で割ると余りは $0,1$ だけ、$8$ で割ると $0,1,4$ だけ。この在庫を持っておくと、「$x^2+y^2=(4$で割って$3$余る数$)$ に整数解なし」のような方程式の解の非存在が、余りの検分だけで示せる。

「全部は調べられないから、余りで有限のグループに落とす」という発想は、整数論の基本である。

別解

$4$ で割った余りで最初から4分類する、表の方法もある。$n$ を $4$ で割った余りは $0,1,2,3$ のどれか。それぞれの $n^2$ の余りを表にする。

• 余り $0$: $n^2$ の余りは $0$
• 余り $1$: $n^2$ の余りは $1$
• 余り $2$: $n^2=(4k+2{)}^2=16k^2+16k+4$ で余り $0$
• 余り $3$: $n^2=(4k+3{)}^2=16k^2+24k+9$ で余り $1$

表の右列に現れるのは $0,1,0,1$。つまり余りは $0$ か $1$ だけだ。

分類を粗くする(偶奇の2分類)か、目的の $4$ に合わせる(4分類)か。どちらでも同じ結論に着く。表方式は機械的に進むぶん、$3$ で割った余りや $8$ で割った余りなど、他の設定にもそのまま横展開できるのが取り柄だ。

方針

解答

⓪ 発想(どう考え始めるか) $6$ の倍数は「$2$ の倍数 かつ $3$ の倍数」($2$ と $3$ は互いに素)。2つを別々に示せばよい。

決め手は因数分解だ。$n^3-n=n(n^2-1)=(n-1)n(n+1)$。連続する3つの整数の積になる。

連続2整数には必ず偶数が、連続3整数には必ず $3$ の倍数がある。だから積は $2$ でも $3$ でも割り切れる。因数分解が「構造」を見せてくれる、という体験の問題だ。

まず因数分解する。

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

これは連続する $3$ つの整数の積だ。連続する $3$ つの整数の中には、必ず偶数が(少なくとも1つ)ある → 積は $2$ の倍数。また、連続する $3$ つの整数の中には、必ず $3$ の倍数がちょうど1つある → 積は $3$ の倍数。

$2$ の倍数でも $3$ の倍数でもあり、$2$ と $3$ は互いに素だから、積は $2\times 3=6$ の倍数だ。よって $n^3-n$ は $6$ の倍数である。$■$

(『$2$ の倍数 かつ $3$ の倍数 ⇒ $6$ の倍数』が使えるのは、$2$ と $3$ が互いに素だから。$4$ の倍数かつ $6$ の倍数でも $24$ の倍数とは限らないのと対照的だ。)

発展。 一般に「連続する $k$ 個の整数の積は $k!$ の倍数」が成り立つ(組合せの数 ${}_n{\mathrm{C}}_k$ が整数であることと同じ内容だ)。この問題の $6=3!$ はその $k=3$ の場合である。

$n^5-n$ は $30$ の倍数、$n^7-n$ は $42$ の倍数。これらも因数分解と余りの分類の合わせ技で示せる、格好の練習台だ。指数と法の間のこの規則性は、フェルマーの小定理につながっている。

別解

因数分解に気づけなくても、余りの分類で地道に証明できる。$6$ で割った余りで、整数を $6$ グループに分ける。$n=6k+r$($r=0,1,2,3,4,5$)の各場合について、$n^3-n$ を $6$ で割った余りは、$r^3-r$ の余りと一致する(展開すると $r^3-r$ 以外の項は全部 $6k$ を因数に持つからだ)。

そこで $r^3-r$ を6通り計算する。

$$0,0,6,24,60,120$$

すべて $6$ の倍数。よって、どの整数 $n$ でも $n^3-n$ は $6$ の倍数だ。本解の因数分解ルートは「なぜ成り立つか」が見える。分類ルートはひらめきゼロでも必ず完走できる。両方持っていると、初見の整除の証明で立ち往生しなくなる。

方針

解答

⓪ 発想(どう考え始めるか) 係数が $37$ と $13$ と大きく、特殊解が目で見つからない。こういうときのための道具が互除法だ。

互除法は最大公約数を求める計算だが、その割り算の式を「逆にたどる」と、$37$ と $13$ の組み合わせで $1$ を作る式が組み上がる。それが特殊解になる。

特殊解が1組あれば、全解はそこからのずれ($13$ と $37$ を単位に動く)で書ける。「1組見つける → ずれで全部書く」の2段構成だ。

互除法で割り算を書く。

$$37=2\times 13+11$$ $$13=1\times 11+2$$ $$11=5\times 2+1$$

余りが $1$ になった(だから $\gcd (37,13)=1$ で、解が存在する)。

逆にたどって $1$ を作る。 いちばん下の式から順に、余りを上の式で置きかえていく。

$$1=11-5\times 2$$

$2=13-1\times 11$ を代入して

$$1=11-5(13-11)=6\times 11-5\times 13$$

$11=37-2\times 13$ を代入して

$$1=6(37-2\times 13)-5\times 13=6\times 37-17\times 13$$

よって $x=6$、$y=-17$ が特殊解($37\times 6+13\times (-17)=222-221=1$)。

全部の解を表す。 もとの式と $37\times 6+13\times (-17)=1$ を辺々引くと $37(x-6)+13(y+17)=0$、つまり $37(x-6)=-13(y+17)$。$37$ と $13$ は互いに素なので $x-6=13t$、$y+17=-37t$。

$$x=6+13t,y=-17-37t(t\text{ は整数})$$

発展。 互いに素な $a,b$ に対して $ax+by=1$ に必ず整数解があるという事実は、整数論の基礎となる定理である。互除法の逆算はその解を実際に構成する手続きだ。

右辺が $1$ でなく $c$ の方程式は、特殊解を $c$ 倍すればよい。また「$37x$ を $13$ で割った余りが $1$」という別解の見方は、「$37$ の逆数(のようなもの)が余りの計算の中に存在する」ことを意味していて、暗号(RSA)の計算にも直結している。

別解

余りの目で見ると、逆算をたどらずに特殊解へ届く道もある。$37x+13y=1$ で、$13y$ の部分は $13$ で割り切れる。だから「$37x$ を $13$ で割った余りが $1$」になればよい。

$37=13\times 3-2$ だから、$37x$ の余りは $-2x$ の余りと同じ。つまり $-2x$ が($13$ で割って)余り $1$、言いかえると $2x$ が余り $12$ になればよい。$x=6$ で $2x=12$。ぴったりだ。$x=6$ を元の式に入れて $y=\frac{1-222}{13}=-17$。

特殊解 $(6,-17)$ が、互除法の逆算と同じものが得られた。「片方の項を余りで考えて消す」この見方は、合同式として整理すると本格的な道具になる。大きい係数を小さい余り($37\to -2$)に置き換えるので、計算が楽になる。

方針

解答

⓪ 発想(どう考え始めるか) 係数が $11$ と $8$ 程度なら、特殊解は目で探せる。$11x$ を $1,2,3,\dots$ 倍して、$1$ との差が $8$ の倍数になる瞬間を待てばよい。

$x=3$ で $33$。$33-1=32=8\times 4$。見つかった。$y=-4$ だ。

特殊解から全解へは「ずれ」で書く。$x$ を $8$ 増やすと $11\times 8$ 増える分を、$y$ を $11$ 減らして打ち消す。この交換が解のすべてである。

特殊解を1組見つける。 試すと $x=3$、$y=-4$ が当てはまる($11\times 3+8\times (-4)=33-32=1$)。

全部の解を表す。 もとの式から $11\times 3+8\times (-4)=1$ を辺々引くと

$$11(x-3)+8(y+4)=0\text{すなわち}11(x-3)=-8(y+4)$$

左辺は $11$ の倍数、$11$ と $8$ は互いに素なので、$y+4$ が $11$ の倍数。$y+4=-11t$ とおくと $y=-4-11t$。戻して $11(x-3)=88t$、$x-3=8t$、$x=3+8t$。

$$x=3+8t,y=-4-11t(t\text{ は整数})$$

(ずれ幅は、$x$ が $y$ の係数 $8$、$y$ が $x$ の係数 $11$。係数がそのまま入れかわる。)

発展。 「解のずれが $(+8,-11)$ の倍数に限る」ことの根拠には、$8$ と $11$ が互いに素であることを使っている。互いに素でない係数(例: $6x+4y=1$)では、そもそも解が存在しない(左辺は必ず偶数)。解の存在条件は「右辺が最大公約数の倍数」だ。

別解の「係数つぶし」は変数の置き換えを繰り返して係数を互除法の要領で縮める方法で、どんなに大きい係数でも確実に特殊解へ着く。思いつきにくい逆算が苦手なら、こちらを主に使ってよい。

別解

目で見つからないときのために、「係数を小さくつぶす」機械的な方法も知っておくとよい。$11=8+3$ に注目して、$11x+8y=3x+8(x+y)$ と書き直す。$u=x+y$ と置けば

$$3x+8u=1$$

係数が $(11,8)$ から $(3,8)$ に縮んだ。この式なら $x=3,u=-1$ が見える($9-8=1$)。$u=x+y=-1$ だから $y=-1-3=-4$。特殊解 $(3,-4)$ が復元できた。

まだ大きければ、同じ置き換えを繰り返して係数をどんどん縮めればよい。これは、互除法の逆算と同じ計算を「前向きに」行っている。どんな係数でも必ず終わる、安心の避難路だ。

方針

解答

⓪ 発想(どう考え始めるか) みかん $x$ 個、りんご $y$ 個として式を立てると $80x+120y=1000$。

まず両辺を $40$ で割って $2x+3y=25$ に軽くする。係数を小さくしてから解くのが、文章題の作法だ。整数解を求めたら、最後に現実の条件($x\ge 1$、$y\ge 1$)でふるいにかける。「式の解」と「問題の答え」の間に、この検問が1つ挟まる。

みかんを $x$ 個、りんごを $y$ 個とすると

$$80x+120y=1000$$

両辺を $40$ で割って係数を小さくする。

$$2x+3y=25$$

$x\ge 1$、$y\ge 1$ の整数解を探す。$2x=25-3y$ より、右辺は正の偶数でなければならない。$25-3y$ が偶数になるのは $3y$ が奇数、つまり $y$ が奇数のとき。また $25-3y\ge 2$(=$2x\ge 2$、$x\ge 1$)から $y\le 7$。

$y=1,3,5,7$ を順に調べる。

• $y=1$:$2x=22$、$x=11$
• $y=3$:$2x=16$、$x=8$
• $y=5$:$2x=10$、$x=5$
• $y=7$:$2x=4$、$x=2$

どれも $x\ge 1$ を満たす。よって買い方は

$$4(\text{通り})$$

発展。 「偶奇で絞る」は合同式(mod 2)のいちばん素朴な形だ。係数が変われば mod 3 や mod 5 で絞ることになる。どの法で見ると片方の変数が消えるか、を探すのが上達の道である。

金額を大きくした「$2x+3y=n$ の解の個数」は、$n$ を動かすと規則的に増えていく。十分大きな $n$ では必ず解がある(作れない最大の金額が存在する)という話題は、フロベニウスの硬貨問題と呼ばれる有名な発展問題だ。

別解

一般解の公式を使わず、「偶奇」で候補を絞って書き出す方法も実戦的だ。$2x+3y=25$ で、$2x$ は必ず偶数、$25$ は奇数。だから $3y$ は奇数、つまり $y$ は奇数でなければならない。さらに $3y<25$ だから $y\le 7$(1個以上なので $y\ge 1$)。候補は $y=1,3,5,7$ の4つだけ。

それぞれ $x=\frac{25-3y}{2}$ を計算すると

• $y=1$: $x=11$、$y=3$: $x=8$、$y=5$: $x=5$、$y=7$: $x=2$

4つとも $x\ge 1$ を満たす。よって $4$ 通り。「偶奇で半分に絞る → 範囲で有限個に絞る → 全部書く」。候補が少ない文章題では、この直接ルートのほうが速くて確実なことも多い。

方針

解答

⓪ 発想(どう考え始めるか) 分数のままでは整数かどうか判定できない。まず分子を分母で割って、「整数+余りの分数」に分ける。

$\frac{2n+7}{n+2}=2+\frac{3}{n+2}$。全体が整数になるのは、残った $\frac{3}{n+2}$ が整数のとき。つまり「$n+2$ が $3$ の約数」だ。整数で考えるので、約数には負も入る。$n+2=\pm 1,\pm 3$ の4つを検分する。

分子を分母で割る。$2n+7=2(n+2)+3$ なので

$$\frac{2n+7}{n+2}=\frac{2(n+2)+3}{n+2}=2+\frac{3}{n+2}$$

$2$ は整数だから、全体が整数になるのは $\frac{3}{n+2}$ が整数のとき。つまり $n+2$ が $3$ の約数。$3$ の約数は正と負を合わせて $\pm 1,\pm 3$(整数 $n$ なので負も考える)。

• $n+2=1$ → $n=-1$
• $n+2=-1$ → $n=-3$
• $n+2=3$ → $n=1$
• $n+2=-3$ → $n=-5$

$$n=-5,-3,-1,1$$

(自然数のときと違い、整数では約数の『マイナス側』も忘れないのがポイントだ。)

発展。 「分けて、残りの分数の分母を約数で縛る」型は、分母が2次式になっても、$xy+x+y$ 型の方程式(因数分解して約数のペアで解く)に姿を変えても、芯は同じだ。定数だけを残して約数の有限性に持ち込む、という設計である。

整数問題の3つの基本の方法「因数分解・余りの分類・範囲で挟む」のうち、この問題で使うのは因数分解(約数)だ。どの神器で斬るかを見立てるのが、整数問題の楽しさだ。

別解

割り算の変形をせず、「約数の関係」だけで攻める道もある。$\frac{2n+7}{n+2}$ が整数ということは、$n+2$ が $2n+7$ を割り切るということだ。一方、$n+2$ は $2(n+2)=2n+4$ も当然割り切る。割り切る2つの数の差も割り切るから

$$(2n+7)-(2n+4)=3$$

も割り切る。つまり $n+2$ は $3$ の約数で、$n+2=\pm 1,\pm 3$。ここからは本解と同じだ。

分数の変形($2+\frac{3}{n+2}$ の形を作る)と、約数の差の議論。どちらも「$n$ を消して定数 $3$ を残す」同じ狙いの2つの言い方である。分子の係数が複雑で割り算しにくいときは、こちらの引き算方式が小回りが利く。

方針

解答

⓪ 発想(どう考え始めるか) $n$ 進法の数は「位の重み」の約束ごとにすぎない。整数部分は右から $1,3,9,27,\dots$($3$ 進法なら)、小数部分は左から $\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots$($2$ 進法なら)。

各桁に重みをかけて足すだけで、$10$ 進法に戻る。小数側の重みが「割る」方向に進むことだけが新しい。整数と小数で、重みの進む向きが逆になる対称性を意識しておくと迷わない。

(1) $3$ 進法の位の重みは右から $1,3,9,27$。$2101_{(3)}$ は右から $1,0,1,2$ なので

$$2\times 27+1\times 9+0\times 3+1\times 1=54+9+0+1=64$$

(2) 小数点以下の位の重みは左から $\frac{1}{2},\frac{1}{4},\frac{1}{8}$。$0.101_{(2)}$ は小数第1位から $1,0,1$ なので

$$1\times \frac{1}{2}+0\times \frac{1}{4}+1\times \frac{1}{8}=\frac{1}{2}+\frac{1}{8}=\frac{4}{8}+\frac{1}{8}=\frac{5}{8}$$

(整数部分は重みが左へ大きく、小数部分は右へ小さくなり、対称的だ。)

発展。 「左から巻き込む」計算は多項式の値を速く求めるホーナー法(組立除法の親戚)と同じものだ。$n$ 進法の数は「$n$ を変数とみた多項式に $n$ を代入した値」なので、多項式の道具がそのまま使える。

$2$ 進法はコンピュータの、$16$ 進法はカラーコード(#FF6600 など)の言葉だ。位取り記数法の原理が分かっていれば、何進法が来ても同じ2つの向き(重みの表・巻き込み)で処理できる。

別解

(1)は重みの表を作らずに「左から巻き込む」計算もできる。先頭の桁から順に、「今までの値を $3$ 倍して、次の桁を足す」を繰り返すのだ。

$$2\to 2\times 3+1=7\to 7\times 3+0=21\to 21\times 3+1=64$$

桁を1つ読むたびに全体が「1桁分だけ左へずれる=$3$ 倍される」ので、この巻き込みで重みが自動的に付く。桁数が多いときは、大きなべき乗($3^5,3^6,\dots$)を書かずに済むのが利点だ。

(2)は、小数点を「持ち上げる」と見通しがよい。$0.101_{(2)}$ は $101_{(2)}$ を $1000_{(2)}=8$ で割ったもの。$101_{(2)}=5$ だから $\frac{5}{8}$。整数の変換に帰着させる作戦である。

方針

解答

⓪ 発想(どう考え始めるか) 循環小数のやっかいさは無限に続くこと。同じ無限部分を持つ2つの数を作って、引き算で消す。

くり返しが2桁だから $100$ 倍だ。$100x-x=45.4545\dots -0.4545\dots =45$ で、$x=\frac{45}{99}=\frac{5}{11}$。(2)は逆向きの問いで、「なぜこの分数は循環するのか」。分母の素因数に注目する。$10$ 進小数で割り切れるのは分母が $2$ と $5$ だけでできているときで、$11$ はそこから外れている。

(1) $x=0.454545\dots$ とおく。くり返しが $2$ 桁なので、$100$ 倍する。

$$100x=45.454545\dots$$

もとの $x=0.454545\dots$ を引くと、小数点以下のくり返しがぴったり打ち消される。

$$100x-x=45\text{すなわち}99x=45$$

よって

$$x=\frac{45}{99}=\frac{5}{11}$$

(2) 既約分数 $\frac{5}{11}$ の分母は $11$。$11$ は $2$ でも $5$ でもない素数だ。分母が $2$ と $5$ だけなら有限小数になるが、$11$ のような別の素因数があると割り切れず、同じ余りがくり返し現れて循環小数になる。だから $\frac{5}{11}$ は循環小数になる。

発展。 有限小数か循環小数かは既約分数の分母だけで決まる。分母の素因数が $2$ と $5$ のみなら有限、それ以外を含めば循環。$10=2\times 5$ という記数法の都合が基準を作っている($3$ 進法なら $\frac{1}{3}$ が有限小数になる)。

「余りの有限性 → 必ず循環」という別解の理屈は、鳩の巣原理の実例だ。周期の長さが分母とどう関係するか($\frac{1}{7}$ は周期6、$\frac{1}{11}$ は周期2)を調べ始めると、整数論の位数の理論につながっていく。

別解

(2)の「なぜ循環するのか」は、実際に $5÷11$ の筆算を回すと理由が分かる。割り算の各ステップで残る「余り」を追う。$50÷11$ で商 $4$・余り $6$。$60÷11$ で商 $5$・余り $5$。次は再び $50÷11$ になる。

余りが $5\to 6\to 5\to 6\to \cdots$ と往復し始めた瞬間、商の桁も $4,5,4,5,\dots$ と循環が確定する。同じ余りからは同じ計算しか続かないからだ。

そして、$11$ で割った余りは $1$〜$10$ の高々 $10$ 種類しかない。割り切れない限り、余りはいつか必ず再登場する。つまり、どんな分数も(割り切れなければ)必ず循環する。

「余りの種類が有限だから循環する」。この鳩の巣の理屈が循環小数の存在理由のすべてである。循環の周期が分母より小さくなることも、同じ理屈から読み取れる。