标签：剩余 frac gcd pmod 定理 扩展 cases inv equiv

前置知识

1.乘法逆元
2.朴素欧几里得

问题

已知\(\begin{cases}x\equiv c_1\pmod{m_1}\\x\equiv c_2\pmod{m_2}\\x\equiv c_3\pmod{m_3}\\...\\x\equiv c_n\pmod{m_n}\end{cases}\)，求未知数\(x\)

求解

若能将这两个式子\(\begin{cases}x\equiv c_1\pmod{m_1}\\x\equiv c_2\pmod{m_2}\end{cases}\)合并为一个，则可以递推合并整个式子，故问题转化为求解

\[\begin{cases}x\equiv c_1\pmod{m_1}\\x\equiv c_2\pmod{m_2}\end{cases} \]

可以转化为$$c_1+m_1k_1=c_2+m_2k_2$$
两边同时除以\(\gcd(m_1,m_2)\)得

\[\frac{m_1k_1}{\gcd(m_1,m_2)}=\frac{c_2-c_1}{\gcd(m_1,m_2)}+\frac{m_2k_2}{\gcd(m_1,m_2)} \]

得

\[\frac{m_1k_1}{\gcd(m_1,m_2)}\equiv \frac{c_2-c_1}{\gcd(m_1,m_2)}\pmod{\frac{m_2}{\gcd(m_1,m_2)}} \]

两边同时除以\(\frac{m_1}{\gcd(m_1,m_2)}\)得

\[k_1=\frac{c_2-c_1}{\gcd(m_1,m_2)}*inv(\frac{m_1}{\gcd(m_1,m_2)})\pmod{\frac{m_2}{\gcd(m_1,m_2)}} \]

故

\[k_1=\frac{c_2-c_1}{\gcd(m_1,m_2)}*inv(\frac{m_1}{\gcd(m_1,m_2)})+{\frac{m_2}{\gcd(m_1,m_2)}}*y \]

代入\(x=k_1m_1+c_1\)得

\[x=\frac{c_2-c_1}{\gcd(m_1,m_2)}*inv(\frac{m_1}{\gcd(m_1,m_2)})*m_1+c_1+{\frac{m_1m_2}{\gcd(m_1,m_2)}}*y \]

即

\[x\equiv{{\frac{c_2-c_1}{\gcd(m_1,m_2)}*inv(\frac{m_1}{\gcd(m_1,m_2)})*m_1+c_1}\pmod{{\frac{m_1m_2}{\gcd(m_1,m_2)}}}} \]

故

\[c_1'={\frac{c_2-c_1}{\gcd(m_1,m_2)}*inv(\frac{m_1}{\gcd(m_1,m_2)})*m_1+c_1} \]

\[m_1'={\frac{m_1m_2}{\gcd(m_1,m_2)}} \]

不断递推直到只剩下一个式子\(x\equiv{c'\pmod{m’}}\)，得\(x=c'+km'\)

标签：剩余,frac,gcd,pmod,定理,扩展,cases,inv,equiv
From： https://www.cnblogs.com/cdx1221/p/17368713.html