問
の 2 の次に大きな素因数を求めよ。
答
素数それぞれを modulo として、 となる k を求める。ところで、
- m は奇数に1を足したものであるから、2を素因数に持つのは自明であり、
- 3の累乗に1を足したものであるから、3を素因数には持たないのも自明である
以下()内は remainder のシークエンス。
mod 5: (3, 4, 2, 1)
よって、mを5で割った余りは2なので、5は素因数ではない。
mod 7: (3, 2, 6, 4, 5, 1)
よって、mを7で割った余りは5なので、7は素因数ではない。
mod 11: (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/4*cで抑えられる)ことから、abc予想における質が1の時の無限の存在を示す例として知られている (a = 1, b = , c=) が、2つ違いの値が共通の大きな因数をもつことは無いので、質にεを加えたときに、増える小さな素因数では追いつかず、収束値としては質が1になりそうな気はする。もちろん、こんな直感などあてにはならないし、分解した片方に因数にそれなりに大きな累乗数が含まれているケースはあるかもしれない(それでは追いつかないだろうとは思うのだけど、それを発見するのは面白そうだ。ちなみにmの形式の値の素因数分解で、3乗以上はn=50の時に53が出現するので無いわけではない)、また、このくらい形式を絞れば証明は存在するのかもしれない。
参考
- Bart de Smit - ABC triples (1.2263)、 (1.2920)、 (1.3111)、 (1.0459)、 (1.2353)、 (1.3235) など、データベースとして探せる ()内は質の値。意外とこれらの中で最大は n=10の時である。
- ABC予想のよくある間違い - tsujimotterのノートブック abc予想についてとっても分かりやすい、すごい!
- 結局突き詰めれば、素数の分布ってのが加法と乗法の組み合わせの生み出す複雑さの最もシンプルな表現の一つだなと気づいてしまって、飽きてしまった。