数学研发论坛

 找回密码
 欢迎注册
查看: 575|回复: 4

[求助] 这个超大反例是怎么得到的?

[复制链接]
发表于 2019-8-20 09:52:49 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
\(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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-20 11:30:56 | 显示全部楼层
辗转相除
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2019-8-20 14:46:56 | 显示全部楼层
  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]]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-8-23 09:44:08 | 显示全部楼层

虽然不是太懂,不过你怎么想到的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-8-23 10:31:35 | 显示全部楼层
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。

至于思路
应该是看到最大公约数直接想到辗转相除吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-11-12 21:55 , Processed in 0.058821 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表