Re: [問題] 98中山資工離散
看板Grad-ProbAsk作者trustn01 (See U in dream)時間15年前 (2009/03/31 00:09)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/3 (看更多)
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：