模运算

Question

有没有办法计算(a mod c)*(b mod c)?

只知道：

• a*b
• c
• d
• ((a mod c)*(b mod c)) mod c
• (a mod d)*(b mod d)

Answer 1

不，这不可能。

这是一个反例：

ab = 1225 = (5)(5)(7)(7)
c = 3
d = 5000
((a mod c)(b mod c)) mod c = 1
(a mod d)(b mod d) = 1225

如果a=25且b=49，则(amodc)(bmodc)=(1)(1)=1

如果a=35且b=35，则(amodc)(bmodc)=(2)(2)=4