推 dendrobium:thx! 03/23 19:58
※ 引述《dendrobium (石斛蘭)》之銘言：
: Prove the following statement by the Pigeonhole Principle:
: If m 屬於 Z+ and m is odd, then there exists a positive integer n
: such that m|(2^n -1).
: 請問這題該怎麼證明呢?
: 有點不知道該怎麼下筆...
存在 n 屬於 Z^+ 使得 m | (2^n)-1
考慮 m+1 個數 : (2^1)-1, (2^2)-1, ... , (2^(m+1))-1
根據鴿籠存在 i =\= j 使得 m | (2^j)-1 - (2^i)-1
=> m | 2^i(2^(j-i)-1)
=> 令 n = j-i 則 m | (2^n)-1
--
歡迎參觀 :)
我的露天拍賣： http://class.ruten.com.tw/user/index00.php?s=outdoorsell
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.78.231