山寨，我冒著被笑話的危險來答你的數字遊戲。

誰讓我除了球迷還是數學迷. 就象逃課, 有賭不下注難過，我是有題不解，有bug不抓也難過. 不過拜托以後不要再出如此boring的題. 要出必須是和體育有關的, 好玩的, 吸引大家一起參加的. 

山寨原題: 數軸上的每一個奇數，無一例外地都是某個梅森數(2^n-1)的因子嗎？

你這個問題隻要學過抽象代數的人都能證明。用一下Euler定理就行。

 

Euler定理如是說:
if A and B are co-prime positive integers (i.e. gcd(A,B) = 1), then there exists a positive integer n, such that A^n = 1 (mod B).
也就是說 B is a factor of A^n - 1. Your question is a special case for A=2,B=odd number.

 

To find n, 質數次方p^k很簡單, n=(p-1)*p^(k-1),  p^k | 2^n - 1

For example, 121=11^2, n=10x11=110, 121 | 2^110 - 1
Another example, 81=3^4, n=2x3^3=54, 81 | 2^54 - 1.

 

對任何奇數，先做prime factorization, a=p1^k1 * p2^k2 * p3^k3... , n = lcm((p1-1)xp1^(k1-1), (p2-1)xp2^(k2-1), ...) 

lcm=least common multiple 

For example, 429 = 3 x 11 x 13, n=lcm(2, 10, 12) = 60, 429 | 2^60 - 1
Another example 117 = 3^2 x 13, n=lcm(2x3, 12) = 12, 117 | 2^12 - 1

Note: such n is not unique. for example 17 | 2^16 -1,  17 | 2^8 - 1.

The beauty of mathematics is existence + uniqueness. 
 

 

所有跟帖： 

• 看不懂。。。 -喜歡豪宅- ♂ (0 bytes) () 05/06/2015 postreply 14:27:05

• 你秒殺山寨好像。。。 -baydad- ♂ (0 bytes) () 05/06/2015 postreply 14:31:31

• “不過拜托以後不要再出如此boring的題” 完了。以後山寨更不出來狗勇士了。 -baydad- ♂ (24 bytes) () 05/06/2015 postreply 14:33:26

• boring的題不許出，狗勇士多多益善 -imayazifan- ♀ (0 bytes) () 05/06/2015 postreply 14:38:05

• 我們這兩天他埋頭出題，都不來狗勇士。被你這麽秒殺，他更不可能來了。 -baydad- ♂ (0 bytes) () 05/06/2015 postreply 14:41:53

• 山寨快點出來謝罪，保證不再不務正業 -imayazifan- ♀ (0 bytes) () 05/06/2015 postreply 14:48:10

• 牛！大深奧了。跟賭不沾一角錢的題目太無聊。 -talkatwxc- ♂ (6 bytes) () 05/06/2015 postreply 14:33:29

• 唱山歌來～～嘿～唉～～哎～～哎～～～～～ -美麻子- ♂ (6 bytes) () 05/06/2015 postreply 14:35:18

• 拜托說中文，或者說英文，要不德文，方言也不是不可以，（不好意思問一下，那個到底是什麽文來的？:)) -Warsteiner- ♂ (0 bytes) () 05/06/2015 postreply 14:38:21

• 我保證以後見著山寨的問題帖繞著走。再不說鳥語了 -imayazifan- ♀ (0 bytes) () 05/06/2015 postreply 14:53:11

• 能不能用上海話（最好是浦東音）來解釋一下好伐：） -I751- ♂ (0 bytes) () 05/06/2015 postreply 15:14:57

• 浦東以前在上海算鄉下？ -baydad- ♂ (0 bytes) () 05/06/2015 postreply 15:16:02

• 現在在某些人眼中也是鄉下LOL -I751- ♂ (0 bytes) () 05/06/2015 postreply 15:23:18

• 我記得我曾經坐船過江去參觀一個鋼廠。那時好像沒說什麽浦東不浦東的。 -baydad- ♂ (77 bytes) () 05/06/2015 postreply 15:27:42

• 上鋼三廠你去視察過？厲害啊 -I751- ♂ (90 bytes) () 05/06/2015 postreply 15:33:43

• 太高溫了。。。記不得是幾廠了。 -baydad- ♂ (0 bytes) () 05/06/2015 postreply 15:35:10

• 老早3分洋鈿一瓶，儂當之才殺啦 -talkatwxc- ♂ (0 bytes) () 05/06/2015 postreply 15:40:57

• 滴格浦東音鵝害真格港勿來 -imayazifan- ♀ (0 bytes) () 05/06/2015 postreply 15:25:08

• 港唔嚟就唔港。。。 -baydad- ♂ (0 bytes) () 05/06/2015 postreply 15:29:53

• 妹妹啊先脫鵝衝碗咖啡，我來告儂奈能港，特二天敵隻股票一息上一息下，我心蕩起蕩來。 -talkatwxc- ♂ (0 bytes) () 05/06/2015 postreply 15:35:32