Re: [理工] [離散]-95海大資工
※ 引述《CMJ0121 (請多指教!!)》之銘言：
: ※ 引述《lovefo (lovefo)》之銘言：
: : Prove or disapprove that given positive integers a and b,
: : a b a mod b
: : ( 2 - 1 ) mod ( 2 - 1 ) = 2 - 1
: : 請問這題怎麼證??
: : 感覺好難!
: 2^a - 1 mod 2^b-1
: == 2^a - 1 mod 2^(b-1)+2^(b-2)+...+1 (因式分解)
: == 2^(a-1)+2^(a-2)+...+1 mod (...) -----式1
: if a<b
: => 2^a-1 == 2^a-1 mod 2^b-1
: == 2^ (a mod b) -1 mod 2^b-1
: if a>=b
: 式1 = 1 + 2 + ... + 2^[(a mod b)-1]
: 想法就是把整串的 2^a -1拆成一堆 2^(b-1)+...+1的段
: 有包含段的都會 mod 0
: 所以剩下的東西就會是長度 a mod b
: e.g.
: a的部分 1 + 2 + 2^2 + ...........+ 2^(b+1-a) + ...+ 2^(a-1)
: b的部分 1 + 2 + 2^2 + ...+ 2^(b-1)
: 故式1 == 2^(a mod b) - 1
: ----
: 解的好爛 = =
分兩個case討論
1. b整除a
=> a=bt t屬於整數
a b bt b
左式: 2 -1 mod 2 -1=2 -1 mod 2 -1=0
bt b bt-1
(因為 2 -1=(2 -1)(2 +...+1) )
a mod b 0
右式: 2 -1=2 -1=0
2. b不整除a
=>存在r!=0, s.t. a=bt+r t,r屬於整數
a b bt+r b r
左式: 2 -1 mod 2 -1=2 -1 mod 2 -1=2 -1
b b
(因為 2 與2 -1互質)
a mod b r
右式: 2 -1=2 -1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.114.53.83
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：