整数論の問題です。(3^n)+1の条件について。

質問

趣味数学なので特に至急というわけでもございませんが、
私はすでにギブアップなのでどなたか助け舟お願いします。
聞けるような人もいないのです。
ネットでちらっと見た問題です。

Q.
(3^n)+1がnで割り切れるような自然数nが無限に存在することを示せ.

自分でも弄ってみました。
nが素数のとき、題意を満たすようなnはn=2しか存在しないようです。
この証明は下の方に書いておきます。

それ以外のときはどうなるのでしょう。皆様のお知恵拝借。
よろしくお願いします。

Prf) (nが素数pのとき)

題意：　(3^p)+1 ≡0 (mod p)

いま、(3+1)^pを2項展開して、
(3+1)^p = 3^p + p・3^(p-1) + … + 3p + 1
この右辺の両端の2項以外のすべてがpの倍数である

よって、
4^p ≡ 3^p + 1 (mod p)
（これはフェルマーの小定理の証明の補題で有名ですね）

上の右辺がpの倍数であれば題意成立
ところで4^pが素数pで割り切れるとき、p=2しかありえない

∴nが素数のとき、(3^n)+1がnで割り切れるようなnはn=2のみ　□

回答No.1

ask-it-aurora · ベストアンサー

きっとユークリッドの素数が無限個存在するという証明のように背理法で証明するのがスマートなのでしょうが，いくつか計算した後に最初に思いついた証明を書きます．実際に条件を満たす無限系列a[n]を構成します．

命題：a[n] = 2*5^n (n ≧ 0) は a[n] | (3^a[n] + 1) を満たす．

証明：nに関する帰納法による．
[n = 0のとき]
a[0] = 2 | 10 = 3^a[0] + 1
より条件を満たす．

[n > 0のとき]
因数分解(x^5 + 1) = (x + 1)(x^4 - x^3 + x^2 - x + 1)を使うと
3^a[n + 1] + 1
=
(3^a[n] + 1)(3^(4*a[n]) - 3^(3*a[n]) + 3^(2*a[n]) - 3^a[n] + 1)
と分解できます．前半部分は帰納法の仮定により2*5^nで割り切れます．後半部分が5で割り切れることは9 ≡ -1(mod 5)に着目すればわかります．したがって全体が2*5^(n + 1)で割り切れます．

以上から帰納法によってすべての自然数nについてa[n]は条件を満たすことがわかります．

## ちなみに条件を満たす自然数は自明な1と上のa[n]以外には計算してみた限りでは見つかりませんでした．というわけで個人的に予想をひとつ．
予想： n | (3^n + 1)を満たす自然数n≠1はn = a[m]の形をしたものに限る．
正しいかどうかは調べてませんが，趣味数学のネタにでもしてみてください．

お礼

素早いご回答ありがとうございます

なるほど、2*5^nでしたか！
4の倍数でない偶数だとか5の倍数大丈夫だとかの条件は見つけてはおりましたが、こんなにスッキリするとは思いませなんだ……

予想のほうで私も精進してまいります。

ありがとうございました！