已知 p,q 互素，n 被 p 除余 r ，被 q 除余 s ，问：n 被 pq 除余几？

luyuanhong

[这个贴子最后由luyuanhong在 2010/10/12 01:15am 第 1 次编辑]

elimqiu

令 d = min{qx-py | qx-py > 0, x,y 是整数}, 则 d = gcd(p,q) = 1
所以有某整数 x, y 使得 qx-py = d = 1
这是 x, y 存在的一个定性证明。