中国剩余定理

2021-01-28  本文已影响0人  摇摆苏丹

表述

m,n为互素的整数,b与c为任意整数。那么同余式组:
\begin{array}{c} x \equiv b \ (mod \ m) \\ x \equiv c \ (mod \ n) \end{array}
恰好有一个解0 \leq x \lt mn

证明

x \equiv b \ (mod \ m)等价于x = b+my,带入x \equiv c \ (mod \ n)my=c-b \ (mod \ n)。根据线性同余式定理,上式的y有唯一解0 \leq y_1 \lt n。又x = b+my,得到0 \leq x_1 \lt mn。因为y_1是唯一的,所以x_1也是唯一的,定理得证。

上一篇下一篇

猜你喜欢

热点阅读