整数の性質 ★★★ 応用の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) $2$ つの余りの条件を、同時に満たす数を探したい。

まず片方の条件を満たす数を小さい順に書き出す。その列の中から、もう片方も満たす数を拾えばよい。$1$ つ見つかれば、次からは $15(=3\times 5)$ ごとに同じ条件の数が並ぶ。$3$ と $5$ の余りが同時に元へ戻るのが、$15$ 進むごとだからだ。

「複数の余り条件は、法の積を周期にして $1$ 本にまとまる」。この構造に気づけるかが主題だ。

(1) まず『$3$ で割ると $2$ 余る数』を小さい順に書く:$2,5,8,11,14,17,20,23,\dots$。この中で『$5$ で割ると $3$ 余る』ものを探すと、$8$($8=5\times 1+3$)が最初だ。

条件を両方満たす数は $3$ と $5$ の最小公倍数 $15$ ごとにくり返す(両方の余りが同時に元に戻るのが、$15$ 進むごとだから)。だから $8$ の次は $8+15=23$。

$$8,23$$

(2) 条件を満たす自然数は $8,23,38,53,68,83,98,113,\dots$ と $15$ おきに並ぶ。$2$ 桁($99$ 以下)で最大のものは

$$98$$

(検算:$98=3\times 32+2$ で余り $2$、$98=5\times 19+3$ で余り $3$。両方の条件に合う。)

発展。 この「複数の余り条件を $1$ 本にまとめる」考え方は、中国剰余定理と呼ばれる。

法どうしが互いに素なら、それぞれの余りをどう指定しても、法の積を周期として解がちょうど $1$ 種類の余りに定まる。$3$ と $5$ は互いに素だから、$15$ を法として余りが $1$ つに決まった。

法が互いに素でないときは、余りの指定に食い違いが起きて解が無いこともある。互いに素という条件を使っていることを意識したい。

別解

別解:合同式で周期をそのまま導く(得意な人向けの視点)。 書き出して拾うかわりに、$2$ つの条件を式で連立してみる。

条件は $x\equiv 2(\mathrm{mod}3)$ と $x\equiv 3(\mathrm{mod}5)$。前者から $x=3k+2$($k$ は整数)と書ける。これを後者へ代入すると $3k+2\equiv 3(\mathrm{mod}5)$、つまり $3k\equiv 1(\mathrm{mod}5)$。両辺に $2$ を掛けると $6k\equiv 2$、$6\equiv 1$ だから $k\equiv 2(\mathrm{mod}5)$。

よって $k=5m+2$、戻すと

$$x=3(5m+2)+2=15m+8.$$

書き出しをしなくても、周期 $15$ と最小の解 $8$ が式から直接出た。$2$ 桁で最大は $15m+8\le 99$ より $m=6$、$x=98$。本解と同じ答えだ。

方針

解答

⓪ 発想(どう考え始めるか) 「解が存在しない」ことは、例をいくら試しても示せない。

そこで、全整数を有限のグループに分ける道具、余り(mod)を使う。$3$ で割った余りで両辺を見比べてみる。左辺 $x^2$ がとりうる余りのリストに、右辺の余りが入っていなければ、等式は決して成り立たない。

「余りの食い違いで、無限にある候補をまとめて否定する」。これが不可能性証明の定跡だ。

整数解 $x$、$y$ があると仮定して、両辺を $3$ で割った余りを比べる。$x^2-3y^2=2$ を移項すると

$$x^2=3y^2+2$$

右辺 $3y^2+2$ を $3$ で割った余りは $2$($3y^2$ は $3$ の倍数だから)。一方、左辺 $x^2$ を $3$ で割った余りは、$0$ か $1$ しかありえない($x$ を $3$ で割った余りが $0,1,2$ のどれでも、$x^2$ の余りは $0,1,1$ になる)。

つまり左辺の余りは $0$ か $1$、右辺の余りは $2$。これは食い違うので、等式は成り立たない。よって、$x^2-3y^2=2$ を満たす整数 $x$、$y$ は存在しない。$■$

(『余りが合わない』の一言で、無限にある候補をすべて否定できる。余りに注目するのは、解の非存在を示すときによく使う方法だ。)

発展。 平方数を $3$ で割った余りが $0,1$ に限られる事実は、平方剰余と呼ばれる考え方の基礎になる。

法を変えると余りのとりうる値も変わる。$4$ で割れば平方数は $0,1$、$8$ で割れば $0,1,4$ しか出ない。どの法で見るかを選ぶのが、非存在証明の腕の見せどころになる。

$x^2-D{y}^2=k$ の形の方程式が整数解を持つかどうかも、適切な法での余りの分析が第一歩になる。ペル方程式と呼ばれる有名な仲間へ続く道だ。

別解

別解:別の法($\mathrm{mod}8$)でも矛盾を出す(得意な人向けの視点)。 $3$ で割るかわりに、$8$ で割った余りで見てもよい。

平方数を $8$ で割った余りは $0,1,4$ の $3$ 種類しかない($0^2,1^2,\dots ,7^2$ を $8$ で割ると、すべてこの $3$ つに収まる)。$x^2-3y^2$ を $8$ で割った余りを、$x^2\in \{0,1,4\}$、$3y^2\in \{0,3,4\}$ の全組み合わせで調べると

$$x^2-3y^2\equiv 0,1,4,5,6(\mathrm{mod}8)$$

の $5$ 種類だけが現れる。右辺 $2$ の余りはこの中に入っていない。だから $x^2-3y^2=2$ は $8$ を法として不可能で、整数解は存在しない。法 $3$ を使う本解とは別の法で見ても、同じく解の非存在にたどり着く。

方針

解答

⓪ 発想(どう考え始めるか) 最大公約数が $12$ という情報を、まず使いやすい形に直す。

$2$ 数を $12a$、$12b$($a$、$b$ は互いに素)と置くのが定跡だ。すると和の条件が $a+b=15$ という小さな式に縮む。あとは「和が $15$ で互いに素な組」の有限リストを吟味するだけになる。

大きな数の問題を、互いに素な小さい数の問題に置きかえる。この流れを自力で通せるかが問われる。

最大公約数が $12$ なので、$2$ 数は $12a$、$12b$ とおける($a$、$b$ は互いに素)。和の条件より

$$12(a+b)=180\text{よって}a+b=15$$

$a\le b$、$a+b=15$、$a$ と $b$ は互いに素、という組を探す。$a+b=15$ の組:$(1,14),(2,13),(3,12),(4,11),(5,10),(6,9),(7,8)$。このうち互いに素でないものを除く。$(3,12)$ は $\gcd =3$、$(5,10)$ は $\gcd =5$、$(6,9)$ は $\gcd =3$ なので除外する。残るのは

$$(1,14),(2,13),(4,11),(7,8)$$

それぞれ $12$ 倍して

$$(12,168),(24,156),(48,132),(84,96)$$

(和が一定のときは、互いに素かどうかの選別が必要。最大公約数がちょうど $12$ になるのは、$a$、$b$ が互いに素なときだけだ。)

発展。 和と最大公約数から $2$ 数を復元できるのは、$\gcd (a,b)=\gcd (a,a+b)$ という性質があるからだ。

和 $a+b$ を固定すると、互いに素という条件は「$a$ が和と互いに素」という条件に言い換えられる。だから候補がすぐに絞れる。最大公約数や最小公倍数と、和や積を組み合わせて $2$ 数を求める問題は、この「互いに素な組へ分解する」書き方がいつでも出発点になる。

別解

別解:「和と互いに素」に読みかえる(得意な人向けの視点)。 $12a$、$12b$ と置き、$a+b=15$、$a\le b$ とするところまで本解と同じ。ここから互いに素の判定を速める。

$\gcd (a,b)$ は $\gcd (a,a+b)=\gcd (a,15)$ に等しい(片方から和を引いても最大公約数は変わらない)。つまり $a$ と $b$ が互いに素であることは、$a$ が $15$ と互いに素であることと同じ意味になる。$15=3\times 5$ だから、$a$ が $3$ でも $5$ でも割り切れなければよい。$a\le b$ より $a$ は $1$ から $7$ の範囲。

• $a=3,5,6$ は $3$ か $5$ の倍数なので除く。
• 残る $a=1,2,4,7$ が条件を満たす。

対応する組 $(1,14),(2,13),(4,11),(7,8)$ を $12$ 倍して

$$(12,168),(24,156),(48,132),(84,96).$$

一つずつ最大公約数を確かめなくても、$a$ と $15$ の関係だけで選別できた。本解と同じ答えに至る。

方針

解答

⓪ 発想(どう考え始めるか) まず $n^2-1$ を $(n-1)(n+1)$ と因数分解する。

$n$ が奇数なら、両隣の $n-1$ と $n+1$ はどちらも偶数だ。しかも差が $2$ の「連続する $2$ つの偶数」になっている。連続する偶数の片方は必ず $4$ の倍数だから、積は $2\times 4=8$ で割り切れる。

「因数分解して連続性を観察する」という整数証明の型に、偶数の連続という見方を重ねれば解ける。

因数分解する。

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

$n$ は奇数なので、$n-1$ と $n+1$ はどちらも偶数だ。しかもこの2つは連続する偶数(差が $2$)。

連続する $2$ つの偶数のうち、一方は必ず $4$ の倍数になる($\dots ,4,6,8,10,\dots$ を見ると、$4$ の倍数が1つおきに現れる)。だから積 $(n-1)(n+1)$ は『$2$ の倍数 × $4$ の倍数』を含み、$8$ の倍数になる。もっとはっきり示すには、$n=2k+1$ とおく。

$$n^2-1=(2k+1{)}^2-1=4k^2+4k=4k(k+1)$$

$k(k+1)$ は連続する $2$ 整数の積だから必ず偶数。よって $4k(k+1)=4\times (\text{偶数})=8\times (\text{整数})$、つまり $8$ の倍数だ。$■$

発展。 奇数を $2$ 乗すると $8$ で割った余りがいつでも $1$ になる、と言いかえてもよい。だから奇数の平方から $1$ を引けば必ず $8$ の倍数になる。

もっと深く割ると、奇数の $2$ 乗を $16$ で割った余りは $1$ か $9$ に限られる。$8$ の倍数までは保証されるが、$16$ の倍数になるとは限らない。

連続する整数の積が階乗の倍数になる、という一般則の一例でもある。連続 $2$ 整数の積は $2$ の倍数、連続 $3$ 整数の積は $6$ の倍数、と続く仲間だ。

別解

別解:奇数の平方を $\mathrm{mod}8$ で調べる(得意な人向けの視点)。 因数分解のかわりに、奇数を $8$ で割った余りだけでまとめて片づける。

奇数を $8$ で割った余りは $1,3,5,7$ のどれか。これらを $2$ 乗して $8$ で割ると

$$1^2=1,3^2=9\equiv 1,5^2=25\equiv 1,7^2=49\equiv 1(\mathrm{mod}8).$$

どの奇数でも平方は $8$ で割ると余り $1$。つまり $n^2\equiv 1(\mathrm{mod}8)$ だから

$$n^2-1\equiv 0(\mathrm{mod}8).$$

場合分けは $4$ 通りだけで済み、連続する偶数を持ち出さずに $8$ の倍数だと分かる。本解と同じ結論だ。

方針

解答

⓪ 発想(どう考え始めるか) $5$ 進法と $8$ 進法の表記を、両方とも $10$ 進法の式に直す。同じ $N$ だから等号で結べる。

未知数は $a$、$b$、$c$ の $3$ つで、式は $1$ 本しかない。ふつうなら解が定まらない。ところが $a$、$b$、$c$ は「$5$ 進法の数字」なので $0$ から $4$ に限られる。しかも先頭の桁は $0$ でない。この強い範囲制限が実質の連立条件になる。

「桁の数字の範囲こそが方程式を解く力」。記数法の問題では、ここが決め手になる。$5$ 進法・$8$ 進法をそれぞれ $10$ 進法の式にする。

$${\overline{abc}}_{(5)}=25a+5b+c,{\overline{cba}}_{(8)}=64c+8b+a$$

両方とも $N$ なので等しい。

$$25a+5b+c=64c+8b+a$$

整理すると

$$24a-3b-63c=0\text{すなわち}8a-b-21c=0\text{つまり}b=8a-21c$$

ここで $a,b,c$ は $5$ 進法の数字だから $0$〜$4$。しかも $a$($5$ 進の先頭)と $c$($8$ 進の先頭)は $1$ 以上。$b=8a-21c$ が $0$〜$4$ に収まる $a$、$c$ を探す。$c=1$ のとき $b=8a-21$。これが $0$〜$4$ になるのは $8a=21$〜$25$、つまり $a=3$($8\times 3=24$、$b=3$)。$c\ge 2$ では $8a-42$ が負になり不適。

よって $a=3$、$b=3$、$c=1$。$N$ は

$$N=25\times 3+5\times 3+1=91$$

(確認:$5$ 進法で $331_{(5)}=91$、$8$ 進法で $133_{(8)}=64+24+3=91$。確かに桁が逆で一致する。)

発展。 桁の順が逆になる数は、回文数(パリンドローム)と近い話題で、記数法を変えると別の見え方をする。

同じ数でも底を変えれば桁の並びが変わる。$91$ は $5$ 進法で $331$、$8$ 進法で $133$ と、ちょうど鏡写しになった。

こうした問題では位取りを底のべきの多項式として書き下し、各桁が底未満という条件で候補を絞るのが共通の型だ。方程式の本数が足りなくても、範囲が残りの条件を補ってくれる。

別解

別解:大きさの評価で $c$ を先に決める(苦手な人向けの実感ルート)。 式を整理する前に、$N$ の大きさを見積もって候補を絞る。

$N$ は $5$ 進法で $3$ 桁 ${\overline{abc}}_{(5)}$。$5$ 進法の $3$ 桁で最大は

$$444_{(5)}=4\times 25+4\times 5+4=124$$

だから、$N\le 124$ が分かる。一方 $N={\overline{cba}}_{(8)}=64c+8b+a$ で、先頭 $c$ は $1$ 以上。もし $c\ge 2$ なら $N\ge 64\times 2=128>124$ となり大きすぎる。だから $c=1$ に決まる。$c=1$ を $64c+8b+a=25a+5b+1$ に入れて整理すると $63+3b=24a$、つまり $b=8a-21$。$b$ が $0$ から $4$ に収まるのは $a=3$($b=3$)だけ。

よって ${\overline{abc}}_{(5)}=331_{(5)}=91$。範囲の評価で $c$ を先に決めると、当てはめがぐっと軽くなる。本解と同じ $N=91$ に至る。

方針

解答

⓪ 発想(どう考え始めるか) 約数 $d$ をとると、$\frac{N}{d}$ も必ず約数になる。この $2$ つを組にする。

ふつうは約数が $2$ 個ずつペアで現れるので、総数は偶数になる。奇数個になるのは、ペアの相手が自分自身になる約数があるときだけだ。それは $d=\frac{N}{d}$、つまり $N=d^2$ のとき。「ペアリングの例外はどこか」という数え方の視点が、そのまま証明の流れになる。

$N$ の正の約数 $d$ を1つとると、$\frac{N}{d}$ も必ず約数になる。この2つを1組として扱う。ふつう、約数は $\left(d,\frac{N}{d}\right)$ の $2$ 個ずつ組になって現れるので、約数の総数は偶数になる。

組にならない(組の相手が自分自身になる)のは、$d=\frac{N}{d}$ のとき。この式を変形すると

$$d^2=N$$

つまり $N$ が平方数で、$d=\sqrt{N}$ がちょうど真ん中の約数として1個だけ余る。このときだけ、約数の個数が『偶数 $+1$』で奇数になる。したがって、約数の個数が奇数になるのは $N$ が平方数のときに限る。$■$

(例:$36=6^2$ の約数は $1,2,3,4,6,9,12,18,36$ の $9$ 個(奇数)。真ん中の $6$ だけ、組の相手が自分自身だ。)

発展。 約数の個数 $\tau (N)=(a+1)(b+1)\cdots$ は「乗法的」な関数だ。互いに素な $m,n$ について $\tau (mn)=\tau (m)\tau (n)$ が成り立つ。

だから $N$ を素因数ごとにばらして掛け合わせれば、約数の個数が出る。同じ仕組みで、約数の総和 $\sigma (N)$ やオイラー関数 $\phi (N)$ も乗法的で、素因数分解から積で計算できる。

「約数が奇数個 $⟺$ 平方数」も、$\tau$ が各因子 $(a+1)$ の積で、その偶奇が指数 $a$ だけで決まる、という乗法的構造の現れ。乗法的関数は整数論で重要な関数の一つだ。

別解

別解:約数の個数の公式で言い切る(得意な人向けの視点)。 ペアを作るかわりに、約数の個数を素因数分解から直接数える。

$N=p^a{q}^b\cdots$ と素因数分解すると、正の約数の個数は

$$(a+1)(b+1)\cdots$$

で与えられる。これが奇数になる条件を考える。いくつかの整数の積が奇数になるのは、掛ける因数がすべて奇数のときに限る。だから $a+1,b+1,\dots$ がすべて奇数、すなわち指数 $a,b,\dots$ がすべて偶数でなければならない。

指数がすべて偶数なら

$$N={\left(p^{a/2}{q}^{b/2}\cdots \right)}^2$$

と書けて平方数になる。逆に $N$ が平方数なら指数はすべて偶数で、個数は奇数。よって約数の個数が奇数になるのは平方数のときに限る。本解と同じ結論だ。

方針

解答

⓪ 発想(どう考え始めるか) 求めるのは自然数解。だから一般解を書く前に、範囲で絞る手が使える。

$y$ について解くと $y=\frac{47-3x}{5}$。これが自然数になるには、$47-3x$ が $5$ の倍数で、しかも正でなければならない。「$5$ の倍数」は余りの条件、「正」は不等式の条件。この $2$ つで $x$ の候補が有限個に落ちる。

不定方程式に自然数という範囲がつくと、この絞り込みそのものが解答の本体になる。$x$ について解く。

$$3x=47-5y$$

$x$ が自然数になるには、右辺 $47-5y$ が『$3$ の倍数』かつ『正』でなければならない。

$3$ の倍数の条件:$47-5y$ を $3$ で割った余りを考える。$47\equiv 2$、$5y\equiv 2y(\mathrm{mod}3)$ なので $47-5y\equiv 2-2y(\mathrm{mod}3)$。これが $0$ になるのは $2y\equiv 2$、つまり $y\equiv 1(\mathrm{mod}3)$。よって $y=1,4,7,10,\dots$。

正の条件:$47-5y>0$ より $y<9.4$、つまり $y\le 9$。合わせると $y=1,4,7$。それぞれ $x$ を求める。

• $y=1$:$3x=42$、$x=14$
• $y=4$:$3x=27$、$x=9$
• $y=7$:$3x=12$、$x=4$

$$(x,y)=(14,1),(9,4),(4,7)$$

発展。 $3x+5y=47$ の整数解は、$1$ つの解を見つければ $x$ が $5$ ずつ、$y$ が $3$ ずつずれる形で無数に並ぶ。今回はそのうち自然数のものだけを取り出した。

係数が互いに素なら、右辺がどんな整数でも整数解は必ず存在する。$3$ と $5$ が互いに素だから解があった。$3$ と $5$ で「表せない最大の金額」は $3\times 5-3-5=7$ という有名な事実にもつながる。額面 $3$ 円と $5$ 円の硬貨で作れない最大値を問う、フロベニウスの問題だ。

別解

別解:$1$ つの解から一般解を作って範囲で絞る(得意な人向けの視点)。 余りで絞るかわりに、まず解を $1$ 組だけ見つけて、そこからすべてを書き出す。

$3x+5y=47$ を見ると、$x=4$、$y=7$ が $12+35=47$ で成り立つ。これをもとになる解にする。係数が $3$ と $5$ だから、$x$ を $5$ 増やして $y$ を $3$ 減らしても和は変わらない。一般解は

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

自然数、つまり $x\ge 1$ かつ $y\ge 1$ を課す。$4+5t\ge 1$ より $t\ge 0$、$7-3t\ge 1$ より $t\le 2$。だから $t=0,1,2$。

$$(x,y)=(4,7),(9,4),(14,1).$$

余りで絞る本解と同じ $3$ 組に至る。

方針

解答

⓪ 発想(どう考え始めるか) $4$ つの数をそのまま前から掛けて展開すると、$4$ 次式の海に溺れてしまう。

そこで「両端どうし」「内側どうし」で組んでみる。すると両方に同じかたまり $n^2+3n$ が現れる。この対称性の発見が全てだ。

かたまりを $1$ 文字 $u$ に置きかえると、積は $u(u+2)$ になる。$1$ を足すと $u(u+2)+1=(u+1{)}^2$ ときれいにまとまる。「対称な組み方で共通のかたまりを作る」。これが式変形の発想になる。

$4$ つの整数を、両端どうし・内側どうしで組む。

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

どちらも $n^2+3n$ を含む。そこで $u=n^2+3n$ と置くと、積は

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

$1$ を加えると

$$u^2+2u+1=(u+1{)}^2$$

$u=n^2+3n$ を戻して

$$n(n+1)(n+2)(n+3)+1=(n^2+3n+1{)}^2$$

$n^2+3n+1$ は整数だから、右辺は平方数だ。$■$

(例:$n=1$ なら $1\times 2\times 3\times 4+1=25=5^2$。確かに $n^2+3n+1=1+3+1=5$ の $2$ 乗になっている。)

発展。 連続する $4$ つの整数の積はいつでも平方数のちょうど $1$ 手前になる。$n(n+1)(n+2)(n+3)+1=(n^2+3n+1{)}^2$ がそれを保証する。

$4$ 数の並びを中心 $n+\frac{3}{2}$ のまわりで見ると、両端どうし・内側どうしがそれぞれ対称に並んでいる。その対称性が、共通のかたまりが現れる理由だ。

連続する整数の積は階乗の倍数になったり平方数の近くに来たりと、きれいな性質を多く持つ。並びの対称性を利用するのが、こうした問題に共通する方法だ。

別解

別解:小さい値で実験して答えを見つける(苦手な人向けの実験ルート)。 うまい組み方が見えないときは、まず具体的な $n$ で計算して規則を探す。

• $n=1$:$1\times 2\times 3\times 4+1=25=5^2$。
• $n=2$:$2\times 3\times 4\times 5+1=121=11^2$。
• $n=3$:$3\times 4\times 5\times 6+1=361=19^2$。

平方の中身 $5,11,19$ を見て、$n^2+3n+1$ に $n=1,2,3$ を入れると $5,11,19$ とぴったり一致する。そこで「$+1$ した数は $(n^2+3n+1{)}^2$ ではないか」と予想する。予想を確かめるため、$(n^2+3n+1{)}^2$ を展開すると

$$(n^2+3n+1{)}^2=n^4+6n^3+11n^2+6n+1.$$

一方 $n(n+1)(n+2)(n+3)=n^4+6n^3+11n^2+6n$ だから、$1$ を足すとぴったり一致する。予想は正しく、本解と同じ答えになる。