Drafts

@cm3 の草稿置場 / 少々Wikiっぽく使っているので中身は適宜追記修正されます。

3^n+1 の素因数

m = 3^{100}+1 の 2 の次に大きな素因数を求めよ。

素数それぞれを modulo として、3^{k} \equiv 1 となる k を求める。ところで、

  • m は奇数に1を足したものであるから、2を素因数に持つのは自明であり、
  • 3の累乗に1を足したものであるから、3を素因数には持たないのも自明である

以下()内は remainder のシークエンス。

mod 5: 3^{4} \equiv 1 (3, 4, 2, 1)

よって、mを5で割った余りは2なので、5は素因数ではない。

mod 7: 3^{6} \equiv 1 (3, 2, 6, 4, 5, 1)

よって、mを7で割った余りは5なので、7は素因数ではない。

mod 11: 3^{5} \equiv 1 (3, 9, 5, 4, 1)

よって、mを11で割った余りは2なので、11は素因数ではない。そもそも、11を素因数に持つことがあり得ないこともわかる。

こうやっていくと、41 を素因数に持つことが分かる。よって 41。

余談

コンピュータならば以下の通り、途中に print 文を入れることにより、2, 41, 133201, 42521761 を素因数に持つことは手元のPCで確認可能。そうすると、残りをオンラインのAPI https://helloacm.com/api/factor/?cached&n=1109667565348268894775749972955601 で分解することにより、18055139801, 61459926512826500975801 という残りの素因数分解も完成する。

# https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
            print([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

同様に、3^{100}-1 についても 2^{4} \cdot 5^{3} \cdot 11^{2} \cdot 61 \cdot 101 \cdot 151 \cdot 1181 \cdot 8951 \cdot 391151 \cdot 394201 \cdot 22996651 という素因数分解が可能である。

3^{2^{n}}-1 = (3^{n}+1)(3^{n}-1) は必ず 2^{3}を因数に持つ(よって、ラジカルが3/4*cで抑えられる)ことから、abc予想における質が1の時の無限の存在を示す例として知られている (a = 1, b = 3^{2^{n}}-1, c=3^{2^{n}}) が、2つ違いの値が共通の大きな因数をもつことは無いので、質にεを加えたときに、増える小さな素因数では追いつかず、収束値としては質が1になりそうな気はする。もちろん、こんな直感などあてにはならないし、分解した片方に因数にそれなりに大きな累乗数が含まれているケースはあるかもしれない(それでは追いつかないだろうとは思うのだけど、それを発見するのは面白そうだ。ちなみにmの形式の値の素因数分解で、3乗以上はn=50の時に53が出現するので無いわけではない)、また、このくらい形式を絞れば証明は存在するのかもしれない。

参考

  • Bart de Smit - ABC triples 1+2^{3}=3^{2} (1.2263)、 1+2^{4} \cdot 5=3^{4} (1.2920)、1+2 \cdot 11^{2}=3^{5} (1.3111)、1+2^{3} \cdot 7  \cdot 13=3^{6} (1.0459)、 1+2^{5} \cdot 5  \cdot 41=3^{8} (1.2353)、 1+2^{3} \cdot 11^{2}  \cdot 61=3^{10} (1.3235) など、データベースとして探せる ()内は質の値。意外とこれらの中で最大は n=10の時である。
  • ABC予想のよくある間違い - tsujimotterのノートブック abc予想についてとっても分かりやすい、すごい!
  • 結局突き詰めれば、素数の分布ってのが加法と乗法の組み合わせの生み出す複雑さの最もシンプルな表現の一つだなと気づいてしまって、飽きてしまった。