这个超大反例是怎么得到的？

mathematica

\(n^{17}+9\) 与 \((n+1)^{17}+9\)不互质的正整数n，

最小的反例是（52个数字）
n=8424432925592889329288197322308900672459420460792433

问题是这个反例怎么得到的？

用mathematica验证得到最大公约数是8936582237915716659950962253358945635793453256935559

参考代码

1. Clear["Global`*"];(*Clear all variables*)
   
2. k=8424432925592889329288197322308900672459420460792433
   
3. Do[g=GCD[n^17+9,(n+1)^17+9];If[g>1,Print[{n,g}]],{n,k-1,k+100}]
   

复制代码

参考资料
https://primes.utm.edu/glossary/page.php?sort=LawOfSmall

https://math.stackexchange.com/q ... rge-counterexamples

lsr314

辗转相除

lsr314

1. f[1] = (x + 1)^17 + 9;
   
2. f[2] = x^17 + 9;
   
3. Do[f[k] = PolynomialMod[f[k - 2], f[k - 1]], {k, 3, 19}];
   
4. a = Denominator[f[18] /. x -> 0];
   
5. b = Numerator[f[19]];
   
6. Print[b/GCD[a, b]]

复制代码

mathematica

lsr314 发表于 2019-8-20 14:46

虽然不是太懂，不过你怎么想到的？

.·.·.

mathematica 发表于 2019-8-23 09:44
虽然不是太懂，不过你怎么想到的？

想明白这个证明是怎么回事了

$gcd(n^17+9,(n+1)^17+9)$
$=gcd(n^17+9,(n+1)^17-n^17)$
$=gcd(n^17+9,1 + 17 n + 136 n^2 + 680 n^3 + 2380 n^4 + 6188 n^5 + 12376 n^6 +  19448 n^7 + 24310 n^8 + 24310 n^9 + 19448 n^10 + 12376 n^11 +  6188 n^12 + 2380 n^13 + 680 n^14 + 136 n^15 + 17 n^16)$
$\le gcd(17*(n^17+9),1 + 17 n + 136 n^2 + 680 n^3 + 2380 n^4 + 6188 n^5 + 12376 n^6 +  19448 n^7 + 24310 n^8 + 24310 n^9 + 19448 n^10 + 12376 n^11 +  6188 n^12 + 2380 n^13 + 680 n^14 + 136 n^15 + 17 n^16)$
$=gcd(153 - n - 17 n^2 - 136 n^3 - 680 n^4 - 2380 n^5 - 6188 n^6 -  12376 n^7 - 19448 n^8 - 24310 n^9 - 24310 n^10 - 19448 n^11 -  12376 n^12 - 6188 n^13 - 2380 n^14 - 680 n^15 - 136 n^16,1 + 17 n + 136 n^2 + 680 n^3 + 2380 n^4 + 6188 n^5 + 12376 n^6 +  19448 n^7 + 24310 n^8 + 24310 n^9 + 19448 n^10 + 12376 n^11 +  6188 n^12 + 2380 n^13 + 680 n^14 + 136 n^15 + 17 n^16)$
通过类似这样的辗转相除，我们可以把两个17次的表达式换成两个16次的表达式（需要注意的是，这里有一处不等号需要验证）
通过十几次辗转相除，我们可以得到$gcd(an+b,c)$这样的形式（以及十几个需要验证的$\le$）
注意到每一次放缩的结果都是，新gcd大于原gcd，也就是我们得到的是一个必要条件，所以我们只需要验证得到的n代入原式得到的gcd是否大于1。

至于思路
应该是看到最大公约数直接想到辗转相除吧