２つの数の最大公倍数探し
2つの整数A,Bの最大公約数gcd(A,B)について不思議なことが
一般にn,cを自然数としr≧2するとき
gcd(n^r+c,(n+1)^r+c)
には予想もつかない変化が起こってくる。
gcd(n^3+2,(n+1)^3+2)
では
n=109*k-58 (k=1,2,3,･･･)に限り109となりそれ以外のnではすべて1(２数は互いに素）となる。
また
gcd(n^5+2,(n+1)^5+2)
では
n=52501*k-12168 (k=1,2,3,･･･)に限り52501となりそれ以外のnではすべて1。
さらに
gcd(n^5+3,(n+1)^5+3)
では
n=41*k-12 (k=1,2,3,･･･)に限り41となりそれ以外のnではすべて1が起きる。
そこで
[1]gcd(n^13+8,(n+1)^13+8)
[2]gcd(n^11+6,(n+1)^11+6)
の変化を見つけて欲しい。
多分
[1] n=32325229*k-3411452 のとき 32325229
[2] n=174878089*k-97513454 のとき 174878089
(追記)
ところで
gcd(n^5+3,(n+1)^5+3)は n=41*k-12 だけではないですね。
n=6311*k-2501のときに6311になると思います。
つまり、gcd(n^5+3,(n+1)^5+3)は
n=258751*k-236008 … (1) のとき 258751
（41k-12と6311k-2501の共通部分）
(1)以外でn=6311*k-2501 のとき 6311
(1)以外でn=41*k-12 のとき 41
上記以外のとき 1
となるのではないでしょうか。
同様に、
[1]は 32325229 の他に 3185062281087740571181
[2]は 174878089 の他に 833544852825037
があると思います。
わ～他の最大公約数もあるんですね。
こんな大きなものは全く予想外でした。
では
gcd(n^17+9,(n+1)^17+9)の1以外の値は見つかりますか？
> gcd(n^17+9,(n+1)^17+9)の1以外の値は見つかりますか？
1658074432246579665377027434627058627273061920217757410397795384493223
352114972939771130346840082354341978716844306415221012933487999
の素因数であることまではわかったのですが、この133桁の数が素因数分解できていないため、具体値は今のところわかりません（しばらくかかりそうですが、現在計算中です）。
[8936582237915716659950962253358945635793453256935559 1]
[13621228647205028136235902561643175420131 2]
の分解になるようです。
なるほど、それでしたら1以外の値は
8936582237915716659950962253358945635793453256935559
だけだと思います。（経験的にp^2のpにはならないようなので）
おそらく
n=8936582237915716659950962253358945635793453256935559*k-○ のときだけ
最大公約数が 8936582237915716659950962253358945635793453256935559
になると思いますが、○を特定する方法はわかりません。
gcd(n^5+3,(n+1)^5+3)
において
n=29(その後41の開きの部分) で41
n=3810(その後6311の開きの部分) で6311
n=22743(その後258751の開きの部分) で258751
その他のnではすべて 1
これを発見するのに終結式が上手く使えることになっていました。
終結式はシルベスター行列Sが使えて
[1 0 0 0 0 1 0 0 0 0]
[0 1 0 0 0 5 1 0 0 0]
[0 0 1 0 0 10 5 1 0 0]
[0 0 0 1 0 10 10 5 1 0]
[0 0 0 0 1 5 10 10 5 1]
[3 0 0 0 0 4 5 10 10 5]
[0 3 0 0 0 0 4 5 10 10]
[0 0 3 0 0 0 0 4 5 10]
[0 0 0 3 0 0 0 0 4 5]
[0 0 0 0 3 0 0 0 0 4]
この行列式が
gp > matdet(S)
%4 = 258751
これを因数分解して
gp > factor(%)
%5 =
[ 41 1]
[6311 1]
から
gcd=41,6311,258751（その他は1すべて)が見れる。
そこでこれをgcd(n^17+9,(n+1)^17+9)に使うと
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 136 17 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 680 136 17 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2380 680 136 17 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 6188 2380 680 136 17 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 12376 6188 2380 680 136 17 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 19448 12376 6188 2380 680 136 17 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 24310 19448 12376 6188 2380 680 136 17 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 24310 24310 19448 12376 6188 2380 680 136 17 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1]
[9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17]
[0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136]
[0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680]
[0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380]
[0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188]
[0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376]
[0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310 19448]
[0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310 24310]
[0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448 24310]
[0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376 19448]
[0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188 12376]
[0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380 6188]
[0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680 2380]
[0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136 680]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17 136]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 17]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10]
これから
gp > matdet(%)
%13 = 8936582237915716659950962253358945635793453256935559
gp > factor(%)
%14 =
[8936582237915716659950962253358945635793453256935559 1]
即ち素数
これって
gcd(n^17+9,(n+1)^17+9)
の値は
n=1,2,3,･････････,8424432925592889329288197322308900672459420460792432 まですべて 1
n=8424432925592889329288197322308900672459420460792433 でいきなり8936582237915716659950962253358945635793453256935559
また次からは 1が続いていき
つぎの8936582237915716659950962253358945635793453256935559だけ離れた
n=17361015163508605989239159575667846308252873717727992 で再び 8936582237915716659950962253358945635793453256935559
以下同様
という物凄い現象が起こることを示しているのですよね。
だれがこれだけ1が続いていて、いきなりビックリするような値が対応してくると想像できるだろうか！
いくら既成の事実が示されていても、数学的帰納法の様な魔法の証明で示さない限り真実ではないと心しておかないといけないんだと
いう警告を与えてくれます。
