※ 引述《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
----
解的好爛 = =
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.14.10