满足 （1）n＜1000（2）66｜n^n+1 的正整数 n 有几个？

luyuanhong

这是网友 问题多答案怪 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

求n的个数，使得 (1) n<1000 (2) 66|n^n+1

luyuanhong

angel_phoenix99

我只能简单判断出能用这个表达的n=66k-1，有15个

awei

陆老师的确厉害！
数列n∧n （mod66）每1320个为一个循环，而我却少了一个0，算成132个。
暂时找不到更好的方法，只能像陆老师那样“硬算了”。

谢芝灵

angel_phoenix99 发表于 2017-4-5 06:22
我只能简单判断出能用这个表达的n=66k-1，有15个

你从费马小定理 66│n^10-1  （因为 n-1为偶，又 3│n^2-1)

很容易证得 n^5-1 与  n^n+1  互质。
所以 只能是 66│n^5+1
由分二步分析
一，  66│n+1 ，得 n+1=66i     i=1，2，3，4，，，，15
能得到 65，131，197，，，，989 十五个。
二，11│n^4-n^3+n^2-n+1
第二步很容易证得 5│n （我这里就略了）
得 11│（5k）^4-（5k）^3+（5k）^2-5k+1   === 化简后，再分析就能得到其它的12个

谢芝灵

从已知 得 （n，66）=1 ，即互质。 .....    （1）
可证明 n+1与 n^n+1/(n+1)互质（证：假设 不互质n+1=ap,  n^n+1/(n+1)=bp，p为奇质数。
有 n^n+1/(n+1)=n^(n-1)-n^(n-2)+n^(n-3)+...-n+1
                       =(ap-1)(n-1)-(ap-1)^(n-2)+(ap-1)^(n-3)+...-(ap-1)+1
                        =ap(整数)+n个1
                        =ap(整数)+n
p│ap(整数)+n 得 p│n ，与 “假设 n+1=ap”矛盾。）......（2）
                    


你从费马小定理 66│n^10-1  （因为 n-1为偶，又 3│n^2-1)

很容易证得 n^5-1 与  n^n+1  互质。[由前面（1），（2）得 n^10-1 与n^n+1 只存在公因子n^5+1 ]
所以 只能是 66│n^5+1
由分二步分析
一，  66│n+1 ，得 n+1=66i     i=1，2，3，4，，，，15
能得到 65，131，197，，，，989 十五个。
二，11│n^4-n^3+n^2-n+1
第二步很容易证得 5│n （我这里就略了）
得 11│（5k）^4-（5k）^3+（5k）^2-5k+1   === 化简后，再分析就能得到其它的12个