作者trustn01 (See U in dream)
看板Grad-ProbAsk
标题Re: [问题] 98中山资工离散
时间Tue Mar 31 00:09:04 2009
※ 引述《decten (聪明豆)》之铭言：
: 2^n-1 = 2^0 + 2^1 +...
: 任何奇数m可以表示成 2^0 + 2^a + 2^b ...
: 则存在 2^n - 1 = ( 2^0 + .. ) + 2^c ( 2^0 + ... ) + ...
: = m + 2^c * m + 2^2c * m + ...
: 德政 XD
: ※ 引述《a534055 (可乐)》之铭言：
: : m是奇数 请用鸽笼原理证明
: : 存在一个正整数n
: : 使得m整除2^n-1
* Let m in Z+ and m is odd. There exists a positive integer n such that m
divides 2^n-1.
* Consider the m+1 positive integers 2^1-1, 2^2-1,…, 2^m-1, 2^m+1-1.
By the principle, we have 1<=s<t<=m+1, where 2^s-1 and 2^t-1 have
the same remainder upon division by m.
* Hence 2^s-1=q1*m+r and 2^t-1=q2*m+r.
* (2^t-1)-(2^s-1)= 2^t-2^s=2^s(2^(t-s)-1)=(q2-q1)m.
* Since m is odd, gcd(m, 2^s)=1.
* Hence, m|2^(t-s)-1, and the result follows with n=t-s.
from: www.mgt.ncu.edu.tw/~ylchen/dismath/chap05.ppt
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.59.200.169