取模运算,求证(x y) mod m =[(x mod m)(y mod m)] mod mmod表示取模运算,5 mod 3 = 2.设 x ,y ,m 都是正整数,求证(x y) mod m =[(x mod m)(y mod m)] mod m非数学专业的,看书(SICP1.2.6 费马检查)的时候看到,搞不明白为什么是这样的.书上只是说这是一个事实,就拿来用了,没有任何推理.
2019-04-11
取模运算,求证(x y) mod m =[(x mod m)(y mod m)] mod m
mod表示取模运算,5 mod 3 = 2.
设 x ,y ,m 都是正整数,求证
(x y) mod m =[(x mod m)(y mod m)] mod m
非数学专业的,看书(SICP1.2.6 费马检查)的时候看到,搞不明白为什么是这样的.
书上只是说这是一个事实,就拿来用了,没有任何推理.
优质解答
设x=am+b,y=cm+d
则xy=(am+b)(cm+d)=acm^2+(ad+bc)m+bd≡bd(mod m)
而x≡b(mod m)
y≡d (mod m)
所以相等.
设x=am+b,y=cm+d
则xy=(am+b)(cm+d)=acm^2+(ad+bc)m+bd≡bd(mod m)
而x≡b(mod m)
y≡d (mod m)
所以相等.