数论趣题

求证：对任何自然数 n，1919190 可以被 n^37 - n 整除。

请问LZ会吗

会，三天内没有人答出的话，我会给提示。

MS应该是“ n^37 - n  可以被1919190整除。”吧？
哪有小的数能被大的数整除的道理？

[quote]原帖由 [i]天宫公主[/i] 于 2006-9-16 23:46 发表
求证：对任何自然数 n，1919190 可以被 n^37 - n 整除。 [/quote]

当 n=1时，n^37 - n=0，原命题不成立！！！ :qDD+

MS2者写反了

1919190=2*3*5*7*13*19*37
N^37-N=N(N+1)(N-1)(N^2+1)(N^2-N+1)(N^2+N+1)(N^4-N^2+1)(N^6+N^3+1)(N^6-N3+1)(N^12-N^6+1)
偶刚初一啊，大师们多指教，不知分解的对不对，希望对各位有参考

楼上其实已经做出来了，最没有技巧的，用楼上的结论和数学归纳法[color=Red]（应该）[/color]即可证明了。

[quote]原帖由 [i]crayfish[/i] 于 2006-9-17 10:54 发表
楼上其实已经做出来了，最没有技巧的，用楼上的结论和数学归纳法[color=Red]（应该）[/color]即可证明了。 [/quote]
请具体些

n=2带入验证即可，
假设m=N时成立，则m=N+1时，代入,可能演算量巨大。
可以试试用余数分别验证每一个质约数。
2,3,很简单。后面的也可能麻烦。

N年没摸笔了，还是等答案舒服......

[quote]原帖由 [i]crayfish[/i] 于 2006-9-17 11:15 发表
n=2带入验证即可，
假设m=N时成立，则m=N+1时，代入,可能演算量巨大。
可以试试用余数分别验证每一个质约数。
2,3,很简单。后面的也可能麻烦。

N年没摸笔了，还是等答案舒服...... [/quote]
2，3，5我都已经证出来了，后面7，13，19，37很麻烦

7=2*3+1
13=2*3*2+1
19=2*3*3+1
37=2*2*3*3+1
因此证明左侧N+1时对2*3/2*3*2等同模(大概是这个名词吧)
f(N+1)=f(N)=1 (mod 2*3*2*3)等等

[quote]原帖由 [i]crayfish[/i] 于 2006-9-17 11:34 发表
7=2*3+1
13=2*3*2+1
19=2*3*3+1
37=2*2*3*3+1
因此证明左侧N+1时对2*3/2*3*2等同模(大概是这个名词吧)
f(N+1)=f(N)=1 (mod 2*3*2*3)等等 [/quote]
这个规律很不错，但是
[color=Red]因此证明左侧N+1时对2*3/2*3*2等同模(大概是这个名词吧)
f(N+1)=f(N)=1 (mod 2*3*2*3)等等[/color]
是不是同余的意思？那么
f(N+1)=f(N)=1 (mod 2*3*2*3)
又是什么意思？
P.S:节约水地，我们私下里PM

[quote]原帖由 [i]夜雨落枫[/i] 于 2006-9-17 10:18 发表
MS2者写反了 [/quote]
Umm.... Prove that for every positive integer n, 1919190 divides n^37 - n.

大家爱怎么翻译怎么翻译吧，我也不知道写反了没有。

[quote]原帖由 [i]天宫公主[/i] 于 2006-9-17 13:49 发表

Umm.... Prove that for every positive integer n, 1919190 divides n^37 - n.

大家爱怎么翻译怎么翻译吧，我也不知道写反了没有。 [/quote]
应该反了
否则会出现那个除数为0的问题

[quote]原帖由 [i]夜雨落枫[/i] 于 2006-9-17 10:43 发表
1919190=2*3*5*7*13*19*37
N^37-N=N(N+1)(N-1)(N^2+1)(N^2-N+1)(N^2+N+1)(N^4-N^2+1)(N^6+N^3+1)(N^6-N3+1)(N^12-N^6+1)
偶刚初一啊，大师们多指教，不知分解的对不对，希望对各位有参考 [/quote]

可以按照这个思路考虑一下：

37 | N^37 - N: 费尔马小定理显然

N^37 - N = N^19.N^18 - N^19 + N^19 - N
= N^19(N^18 - 1) + N^19 - N
= N^19(N^phi(38)-1) + N^19 - N
= 0 (欧拉定理) + 0 (费尔马小定理) mod 19
因此，19 | N^37 - N。

[quote]原帖由 [i]天宫公主[/i] 于 2006-9-17 15:56 发表


可以按照这个思路考虑一下：

37 | N^37 - N: 费尔马小定理显然

N^37 - N = N^19.N^18 - N^19 + N^19 - N
= N^19(N^18 - 1) + N^19 - N
= N^19(N^phi(38)-1) + N^19 - N
= 0 (欧拉定理) + 0 (费尔马小 ... [/quote]
汗，偶刚初一，费尔马小定理知道，但是什么欧拉定理就不清楚了……

[quote]原帖由 [i]天宫公主[/i] 于 2006-9-17 15:56 发表


可以按照这个思路考虑一下：

37 | N^37 - N: 费尔马小定理显然

N^37 - N = N^19.N^18 - N^19 + N^19 - N
= N^19(N^18 - 1) + N^19 - N
= N^19(N^phi(38)-1) + N^19 - N
= 0 (欧拉定理) + 0 (费尔马小 ... [/quote]
显然，N^19 - N divides N^37 - N

[quote]原帖由 [i]天宫公主[/i] 于 2006-9-17 15:56 发表


可以按照这个思路考虑一下：

37 | N^37 - N: 费尔马小定理显然

N^37 - N = N^19.N^18 - N^19 + N^19 - N
= N^19(N^18 - 1) + N^19 - N
= N^19(N^phi(38)-1) + N^19 - N
= 0 (欧拉定理) + 0 (费尔马小 ... [/quote]

令f(N)=N^37-N
f(0)=f(-1)=f(1)=0 由因式定理 (N-1)N(N+1)为f(N)因式 故2，3|f(N)

由公主证明19,37|f(N)

N^37-N=N^13.N^24 - N^13 + N^13 - N
= N^13(N^24 - 1) + N^13 - N
=N^13(N^12-1)(N^12+1)+N^13-N
= N^13(N^phi(13)-1)(N^12+1) + N^13 - N
=0 (欧拉定理) + 0 (费尔马小定理) mod 13
因此，13 | N^37 - N。

同理可证，5|f(N)。

N^19-N=N^7(N^phi(7)-1)(N^6+1)+N^7-N
故，7|N^19-N, 因为N^19-N|N^37-N 故7|N^37-N

综上 2,3,5,7,13,19,37均整除N^37-N f(2)>1919190 故1919190|f(N)

:P

[[i] 本帖最后由 青木风亮 于 2006-9-17 21:56 编辑 [/i]]

青木正解，基本上就是这样的。:q```+

其实拿归纳法硬算也不是没希望的。

回复 #14 天宫公主 的帖子

仅仅从翻译角度，应该是：n^37 - n能够被1919190整除:lol: