・最大公約数を求めて                      GAI 氏

 Xに、ある自然数を用いるとき、つぎの2つの数には互いに素でないような 1 ではない最大
公約数が出現できます。さて、そのXと最大公約数は何となるでしょうか?

(1) gcd(X^11+1,(X+1)^11+1)

(2) gcd(X^11+2,(X+1)^11+2)

(3) gcd(X^11+3,(X+1)^11+3)

(4) gcd(X^11+4,(X+1)^11+4)

(5) gcd(X^11+5,(X+1)^11+5)

(6) gcd(X^17+9,(X+1)^17+9)  (*これは超難問)


 らすかるさんからのコメントです。(令和3年5月26日付け)

 (1)は、X=10 のとき、23

 (2)は、X=1234 のとき、1321  (いずれも一例)

というのは探索してすぐにわかったのですが、超難問に行くよりずっと前の(3)でつまずいてし
まいました。((3)は解があるならばXは8億以上で最大公約数は300万以上)

 うまく論理的に考えて見つける方法も思いつきません。解を見つけるには、どのように考え
れば良いのでしょうか。


 GAI さんからのコメントです。(令和3年5月27日付け)

 (3)は、X=1994117680 のとき、14188284463 で、やっと互いに素ではなくなると思います。

 ずっと前に、gcd(n^5+5,(n+1)^5+5) が、n=1,2,3,・・・,2502110 のそのほとんどが1で互いに素
の状態であるのに、唯一 n=533360(次は、n=2502111)であるときだけ、gcdが 1968751 とな
り、この2数が関係性を有するのが不思議で、このサイトで質問していたら、らすかるさんか
ら、次の様な方法で解説してもらっていました。(→ 参考:「質問に対する回答(20)」)

 A=(n+1)^5+5 、B=n^5+5 とおき、ユークリッドの互除法を用いて、5回目の作業で最大公
約数に相当する部分の値として、G=96468799/156950784 を求め、その分子を因数分解さ
れ、 96468799=7^2*1968751 そして、n^5+5≡0 (mod 1968751) から

 n=96502 、533360 、533361 、1066696 、1707583

を導かれ、(n+1)^5+5 (mod 1968751) も 0 を起こすものが、上記5つの中で、n=533360 であ
ると導かれて解説されていました。

 なるほど、これで、次のnは、533360+1968751=2502111 なのかと納得しました。

 そこで、この手法を見習い、自分なりに改良をいくと、gcdに相当する1968751が2つの式

 x^5+5 、(x+1)^5+5

の終結式 polresultant(x^5+5,(x+1)^5+5,x) で求まることがわかりました。

 これらを含め、プログラムを組むと(PARI/GPで)、polresulant(x^11+3,(x+1)^11+3) から

%=577824313765319159023

が手に入り、これを因数分解して、

=14188284463*40725453121

 ここで、p1=14188284463 と置くと、

setintersect(lift(polrootsmod(x^11+3,p1))~,lift(polrootsmod((x+1)^11+3,p1))~) から、

%=1994117680

 また、p2=40725453121 と置くと、

setintersect(lift(polrootsmod(x^11+3,p2))~,lift(polrootsmod((x+1)^11+3,p2))~) から、

%=40515509471

が得られます。確かに、

gp > gcd(1994117680^11+3,1994117681^11+3)
%166 = 14188284463

gp > gcd(40515509471^11+3,40515509472^11+3)
%167 = 4072545312

ですから、Xに小さいものから順に検索していくと先に、X=1994117680で gcd=14188284463
が起こることになります。

 正に、らすかるさんから解説してもらった処方を行っただけです。

 以下、(4)、(5)、(6) も数字は大きくなっていきますが、同じプログラムで得られると思います。

 答えは次を参考に...。(→ 「A255854」、「A255855」、「A255859」、「A010034」)


 らすかるさんからのコメントです。(令和3年5月27日付け)

 まさか自分が前に言ったことだったとは。でも、それを忘れていても同じことは考えるもので、
実は分子を素因数分解して、14188284463 という値は見つけていました。それなのに「最大
公約数が14188284463になるものはない」と思ってしまったのは、単に自分のプログラムにバ
グがあって、見つからなかっただけでした。今修正したらちゃんと見つかりました。

(バグに気づかなかったのは、(1)では値が小さく、きちんと求まっていたためです。
14188284463>2^32が罠でした。)

 14188284463 以外も調べ続けていたのは、分子の素因数でないものが出てくることがある
からです。

 (1)の分子を素因数分解すると、 23^3*31^2*89*109^2*151^2*653^2 なのですが、最大
公約数が上記の素因数に含まれない

 X=52 のとき、gcd=67
 X=137 のとき、gcd=199

などが見つかります。

 よって、(3)の場合も、14188284463以外もあるかも知れないと思って、しばらく探していたの
でした。



              投稿一覧に戻る