为什么0<i<j, p*i%n == p*j%n, 会得出 p*（j-1）%n == 0？
来源：3-1 最大公约数算法
shuoLMS
2021-06-29
为什么0<i<j, pi%n == pj%n, 会得出 p*（j-1）%n == 0？
写回答
1回答
-
javaman
2021-06-30
是p * (j - i) % n == 0吧？
因为p * i % n = p * j % n
所有
我们用同余符号，所有数都是对n取模后的，用"=="表示对n取余数后相同。
我们有p * i == p * j (mod n)
即 p * (j - i) == 0 (mod n)
同余式可以移项
00
相似问题