| 至少有3个方法可以推广至任何素数甚至所有的数 |
| 送交者: gugeren 2020月07月04日21:41:45 于 [灵机一动] 发送悄悄话 |
| 回 答: 趣味的数学-383 由 gugeren 于 2020-07-02 22:53:01 |
|
1】利用二项展开式，由于只有展开式的最后一项决定余数，所以可以一再利用这个方法来找余数。 例如，2^1000 = (2^10)^100 = 1024^100 = (3x341+1)^100 ≡ 1^100(mod 3)≡ 1(mod 3) 2】利用：如一数M被p除的余数是a，另一数N被p除的余数是b，则M*N被p除的余数是a*b。这个很容易证明的。 3】最强大的是：Fermat's little theorem: a^(p-1)≡ 1(mod p)，见 https://en.wikipedia.org/wiki/Fermat%27s_little_theorem |
|
|
|
|
 |
 |
| 实用资讯 | |
