問題はこちら（画像をクリックするとPDFファイルで開きます。）
a^{n}-1 という形を含む整数問題を扱います。
今回は2^{n}-1 というタイプを例題に持ってきました。
2^{n}-1 という形はメルセンヌ素数や完全数などとの絡みもあり、奥が深いですが、それは後々扱おうかなと思います。
本問は適度な誘導がついているため、標準的な難易度に仕上がっていると思います。
（実際には差が付くレベルの問題で、決して簡単ではないとは思いますが）
ひとまず、本問を解いたあと、本問をもう少し難しくアレンジしてみるという構成で進めます。
なので、まずは一通り自力で解いてみてください。
普通に解くだけでも、色々なモノの見方ができて得るものは多いはずです。
（以下ネタバレ注意）
+ クリック（タップ）して続きを読む
以下使用する文字は断りがない限り整数を表すものとします。
(1) について
ひとまず、条件から n=2k とすると
2^{n}-1=2^{2k}-1 となり、
4^{k}-1
という形となります。
ここからの料理の仕方は様々です。
二項定理の活用
4^{k}-1=(3+1)^{k}-1
と見て二項展開をするというのも常套手段の一つです。
本当に二項展開してもいいですが、3 の倍数は無視して余りだけ取り出すというのであれば合同式を用いて
(3+1)^{k}-1 \equiv 1^{k}-1 \pmod 3
と表現すればスッキリします。
因数分解の活用
重要
a^{n}-1=(a-1)(a^{n-1}+a^{n-2}+\cdots+a+1)
という因数分解を利用して
4^{k}-1=(4-1)(4^{k-1}+4^{k-2}+\cdots+4+1)
と見るのも有力な路線の一つでしょう。
(2) について
これまた、色々な方針が考えられます。
正の整数 a と b が互いに素であるとは
a と b の最大公約数が 1
ということです。
ここをどう掘り下げるかで、方針が分かれます。
最大公約数に注目すると
2^{n}+1 と 2^{n}-1 の最大公約数が 1 を示せばよいわけですから、最大公約数に迫る有力なアプローチとして
ユークリッドの互除法
をインスピレーションするのも一つです。
-
-
参考ユークリッドの互除法【原理の証明とイメージ】【2005年度 広島市立大学】
問題はこちら（画像をクリックするとPDFファイルで開きます。） ２つの正整数の最大公約数を求めるときに用いられる「ユークリッドの互除法」と呼ばれるアルゴリズムについて、原理と証明を考えてみます。 古典 ...
続きを見る
互いに素であるということを言い換えると
a と b が互いに素であるということは
a と b が 1 以外の公約数をもたない
という否定的な命題です。
そうなってくると、背理法という路線で考える人も出てくると思います。
(3) について
いよいよ、本問のオチ的な問題です。
p , q が素数ということで、素数が絡んだ等式について考えます。
素数の扱いについては細々としてマニュアル化するとかえって面倒なのですが、素数が絡んだ等式について
偶奇に注目する
というのはよくやるものの見方の一つです。
そうなると、
- p=2 のとき
- p \geq 3 のとき
というように分けたくなります。
p=2 のときは個別検証なので、チャッチャと終わらせます。
p \geq 3 のときは p は奇素数ということになります。
そうなると 2^{p-1}-1 は 2^{偶数}-1 という形となるため、(1) が効いてきて 3 の倍数ということが言えます。
必然的に右辺の pq^{2} も 3 の倍数ということになり、p , q が素数ということも考えると
p=3 または q=3
ということが言えます。
p=3 のときは個別検証なので、さっさと終わらせます。
q=3 のときは厄介で
2^{p-1}-1=9p
という方程式が残ります。
こいつの処理に対して、再び２路線考えられます。
(2) を活かす路線
p が奇素数のときを考えていたわけですから、p-1 は偶数です。
そこで、p-1=2m などとおくと、2^{2m}-1=9p となり、
(2^{m}+1)(2^{m}-1)=9p
と因数分解できます。
ここからは整数問題の基本の一つである
積の形からの約数の拾い上げ
という方針で、右辺の約数を拾って、2^{m}+1 , 2^{m}-1 に割り振ります。
ここで (2) の結論である、2^{m}+1 , 2^{m}-1 が互いに素であることが効いてきます。
よくよく考えると
2^{p-1}-1=9p
という方程式ですが、これを見て「嫌だなぁ」と思った人も多いと思います。
その「嫌」の中身は
「指数 p と裸の p が入り混じっている」
ということでしょう。
ただ、これを逆手にとって、
左辺は指数関数的だから、あるところから爆発的に増えて、右辺の１次式程度では追いつかないのでは
と見ることができればしめたものです。
実験してみると p=7 でちょうど等号が成立します。
こうなってくると素数 p という設定に意味はなく、8 以上の整数 N に対して
2^{N-1}-1 \gt 9N
であることを示せばおしまいです。
もちろん、その手法は帰納法でしょう。
本問をもう少し難しくアレンジすると
本問の (3) と同じことを違う言い回しで問いにすると
\displaystyle \frac{2^{p-1}-1}{p} が平方数となるような素数 p を求めよ。
というように q を消してしまうと、恐らく得点率はグッと下がるでしょう。
そう考えると本問の出題の仕方は九州大学の優しさといえるかもしれません。