中国剩余定理(crt)学习笔记

 

前置技能点:

维基百科_裴蜀定理(贝祖等式)

对任何整数a, b和它们的最大公约数d,关于未知数xy线性丢番图方程(称为裴蜀等式):ax+by=m

有整数解时当且仅当md倍数。裴蜀等式有解时必然有无穷多个整数解,每组解xy都称为裴蜀数,可用扩展欧几里得算法求得。

特别地,方程 ax+by=1 有整数解当且仅当整数ab互素。(kk:因为1(m=1)只可能是1(d=1)的倍数,也就是说gcd(a,b)=1,即a,b互质)

 

 

维基百科_扩展欧几里得算法

已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式

ax + by=\gcd(a, b).
通常谈到最大公约数时,我们都会提到一个非常基本的事实:给予二整数a、b,必存在有整数x、y使得ax + by = gcd(a,b)[1]

有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。

例子:

求二元一次不定方程{\textstyle 47x+30y=1}的整数解。

  • 47 = 30 * 1 + 17
  • 30 = 17 * 1 + 13
  • 17 = 13 * 1 + 4
  • 13 = 4 * 3 + 1

然后把它们改写成“余数等于”的形式

  • 17 = 47 * 1 + 30 * (-1) //式1
  • 13 = 30 * 1 + 17 * (-1) //式2
  • 4 = 17 * 1 + 13 * (-1) //式3
  • 1 = 13 * 1 + 4 * (-3)

然后把它们“倒回去”

  • 1 = 13 * 1 + 4 * (-3) //应用式3
  • 1 = 13 * 1 + [17 * 1 + 13 * (-1)] * (-3)
  • 1 = 13 * 4 + 17 * (-3) //应用式2
  • 1 = [30 * 1 + 17 * (-1)] * 4 + 17 * (-3)
  • 1 = 30 * 4 + 17 * (-7) //应用式1
  • 1 = 30 * 4 + [47 * 1 + 30 * (-1)] * (-7)
  • 1 = 30 * 11 + 47 * (-7)

得解x=-7, y=11。

 

Acdreamer的博客_中国剩余定理

维基百科_中国剩余定理

用现代数学的语言来说明的话,中国剩余定理给出了以下的一元线性同余方程组

(S) : \quad \left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end{matrix} \right.

有解的判定条件,并用构造法给出了在有解情况下解的具体形式。

重点是:中国剩余定理是一种构造法。

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz