京大作問サークルの整数を解いた【神解法あり】

Twitterを眺めていたらこんな問題が流れてきた。

1=8ᵃ-9ᵇ7ᶜを満たす自然数組(a,b,c)を全て求めよ.
(京大数学作問サークル)

という問題。京都大学が1897年に出来たのがこの式の由来らしい。

問題を解く時の思考回路を文字に起こしつつ、最後に答案にスッキリまとめようと思う。

それじゃあ、早速解いていこう。

8ᵃ=2³ᵃとかにして因数分解公式？指数が偶数であることを示してから1を使って因数分解公式とかかな。できればb,cともに偶数なら楽だけど。
aが飛び抜けてでかいけど、b,cに関して上から抑える何かがあればラッキー

そんなことふわふわ思いながらも、やはり最初はお馴染みの大鉄則である。

偶奇→mod→因数分解

の流れを脳死で調べてみよう。

偶奇はパスでmodを調べよう。例の如く7,8,9あたりかな。まあ一旦脳死でやってみよう。

mod7
1≡1
mod8
1≡-(-1)ᶜよりc奇数
mod9
1≡(-1)ᵃよりa偶数

次は因数分解
a=2kとおいて因数分解すると

(8ᵏ-1)(8ᵏ+1)=9ᵇ7ᶜ

大鉄則パート終わり。標準レベルの整数問題だとここで終わることも少なくはないが、今回はもう一踏ん張り。

愚直にやるなら8ᵏ-1=3ᵈ7ᵉとして〜とかかな？
それか、8ᵏ-1と8ᵏ+1は9ᵇ7ᶜの約数で差が2の〜
とか、gcd(最大公約数)を持ち出す？

なんてことがふわっと頭に浮かぶ。これは経験則なので、問題をたくさん経験してもらうしかない。同じようなこと、+αが思い浮かばれた諸君はグッド。脱帽です。

約数で差が2って結構特徴的だと思う。
下から順に書き出してみよう。
1,3,7,9,21,27,…
うーん。イマイチ。b=c=1が解ってことしかわからん。

次にgcdについて。
普段整数問題を解く時gcdを意識することって余りないと思う。これが差がつくポイント。

gcdを意識せよ！

gcd(8ᵏ-1,8ᵏ+1)=gcd(8ᵏ-1,2)=(2の約数)
となるがk自然数よりgcd=1つまり

8ᵏ-1と8ᵏ+1は互いに素

である。

(8ᵏ-1)(8ᵏ+1)=9ᵇ7ᶜ=3²ᵇ7ᶜ
であったから、素因数3と7を綺麗に分け合うということがわかった。式にすると、

(8ᵏ-1,8ᵏ+1)=(3²ᵇ,7ᶜ),(7ᶜ,3²ᵇ)

である。文字が３つあるがk,b,cのうち一つでも分かれば他の２つがわかることを念頭に置いておいて欲しい。

さあ、ここで神解法を紹介しよう

素数の整数乗は割り算で解決！

だ。

8ᵏ-1=2³ᵏ-1=(2ᵏ-1)(4ᵏ+2ᵏ+1)
と因数分解できるよね。ここでこの式の最右辺に注目して欲しい。(2ᵏ-1)も(4ᵏ+2ᵏ+1)も素因数が3または7のみでできており、2ᵏ-1<4ᵏ+2ᵏ+1である。ここで割り算が登場する。

なんのいい読者なら気づいてると思うが、小さい方を分母に持ってくると、その分数式も自然数になるはず。

(4ᵏ+2ᵏ+1)/(2ᵏ-1)=2ᵏ+2+3/(2ᵏ-1) ∈ℕ
よって3/(2ᵏ-1)は自然数だから少なくとも
3≥2ᵏ-1 ∴k=1,2 (必要条件)

割り算するだけでkが2通りに絞られた。しかもただの必要条件であることに気づいただろうか？3or7の冪乗であるという条件よりもはるかに緩い「自然数」という条件で話を進めてもこの制度で絞り込みができる。もっというと最後は分数が「1以上」という条件でk=1,2を導いた。脳みそにも腕の筋肉にも優しい。

(8ᵏ-1)(8ᵏ+1)=3²ᵇ7ᶜを考慮して
(i)k=1のときつまりa=2のとき、
7･9=3²ᵇ7ᶜ ∴b=1,c=1
(ii)k=2のときつまりa=4のとに
63･65=3²ᵇ7ᶜ
素因数が不一致、よって不合理

以上より(a,b,c)=(2,1,1)のみが解となるとわかる。

最後に「mod調べずに３乗公式使うっていうのは考えなかったの？」とモヤモヤしている読者に向けて。今回はスルスル解けたからいいけど、解けなかった時に考えようかなーと思っていた。またこの解法を選んだとしても、同じような流れでgcdを考えることになるが、互いに素になるとは限らない。結局うまくは行かない。

ここからは答案として綺麗にまとめてみる。

答案

1=8ᵃ-9ᵇ7ᶜ

9を法にすると，1≡(-1)ᵃよりa=2k (k∈ℕ)
よって与式は次のように変形できる.
1=(8ᵏ)²-9ᵇ7ᶜ
9ᵇ7ᶜ=(8ᵏ-1)(8ᵏ+1)

ここで，gcd(8ᵏ-1,8ᵏ+1)=gcd(8ᵏ-1,2)=(2の約数)
しかし，これらともに偶数でないからgcd=1
ゆえに，8ᵏ-1,8ᵏ+1は互いに素．
よって，8ᵏ-1=9ᵇと8ᵏ-1=7ᶜのときを考えれば良い.

ここで,
8ᵏ-1=2³ᵏ-1=(2ᵏ-1)(4ᵏ+2ᵏ+1)
と因数分解できる.
2ᵏ-1,4ᵏ+2ᵏ+1ともに素因数が3のみまたは7のみであり，2ᵏ-1<4ᵏ+2ᵏ+1である．

よって，
(4ᵏ+2ᵏ+1)/(2ᵏ-1)=2ᵏ+2+3/(2ᵏ-1) ∈ℕ
つまり，3/(2ᵏ-1)∈ℕだから，
3≥2ᵏ-1 ∴k=1,2 (必要条件)

(8ᵏ-1)(8ᵏ+1)=3²ᵇ7ᶜに注意して

(i)k=1のときつまりa=2のとき、
7･9=3²ᵇ7ᶜ ∴b=1,c=1

(ii)k=2のときつまりa=4のとに
63･65=3²ᵇ7ᶜ
素因数が不一致、よって不合理

以上より求める自然数組は(a,b,c)=(2,1,1)