标题: 哈佛大学博士考题 [打印本页]

---

作者: 天宫公主    时间: 2004-12-25 17:33

上次出级数题目许多朋好象没过瘾, 这次给个有相当难度的.

已知, 2^37 - 1= 137438953471是和数, 它有一个在200和300之间的质因数; 求出此数.

当然朋友们可以用穷举, 不过最好不要用.

注: 此题来自于http://www.math.harvard.edu/graduate/quals/qs97.pdf

---

作者: 瓦灰    时间: 2004-12-25 17:37

和数?应该是合数吧.

---

作者: 青石    时间: 2004-12-25 17:45

这个题目有意思

---

作者: 青石    时间: 2004-12-25 18:01

223

哈哈 200——300间的第二个素数

---

作者: 瓦灰    时间: 2004-12-25 18:04

一看楼主出这个题我就想到了著名的默森数,我还以为楼主要问M37是合数还是质数,如果是合数请把它写成因子相乘的形式,要是这样问我们就臭大了.

---

作者: victorcheng333    时间: 2005-2-27 00:02

設p是那個素數,

則從p l 2^37-1知道

2^37=1(mod p)

同時2^(p-1)=1(mod p)

所以猜p-1=37k
在200與300之間37的倍數有222,259和296
而其中260和297都是合數,只有223是素數,
下面證明223 l 2^37-1

2^8=33(mod 223)
2^16=1089=-26(mod 223)
2^32=676=7(mod 223)
2^37=7X32=1(mod 223)
因此223 l 2^37-1

前幾天剛學到 Euler 用來證明2^32+1是合數的方法，剛好在這是也用得上

---

作者: 青木风亮    时间: 2005-2-27 14:00

我觉得victorcheng333对了 天公来说一下

---

作者: 天宫公主    时间: 2005-2-27 19:33

青石解出的比较早，victorcheng写出了详细的步骤。

---

欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/)

Powered by Discuz! 5.0.0