同余问题三种类型例题

同余问题三种类型例题类型一求最小正整数解

1.给定不等式其中为正整数,求$ax\equiv b\pmod{m}$,$a,b,m$最小正整数解$x$.举例解方程$37x\equiv2\pmod{ll}$.解法由于所以原方程可以化为$37\equiv4\pmod{ll}$,进一步变形得到因此$4x\equiv2\pmod{ll}$,$x\equiv6\pmod{ll}$,是满足条件的最小正整数解$x=6$类型二求通解

2.给定线性同余方程其中为正$ax\equiv b\pmod{m}$,$a,b,171$整数，求其通解其中是的一个特解，$x=n+\frac{m}{d}t$,$n$$x$为$的最大公约数,$d=\gcda,m$a,m$$t\in\mathbb{Z}$.举例解方程$14x\equiv21\pmod{49}$.解法首先利用辗转相减法求出和的最大公约数$14$$49$，然后对原方程两边同除以得到在$d=7$7$2x\equiv3\pmod{7}$□模意义下,构成了完全剩余系,因此我们可以将7$\{0,1,234,5,6\}$上式化为因此特解通解为$x\equiv2\pmod{7}$$x=2$,$x=2+7t$0o类型三中国剩余定理问题

3.给定线性同余方程组$$\begin{cases}x\equiv a_l\pmod{m_l}\\x\equiva_2\pmod{m_2}\\\vdots\\x\equiv a_k\pmod{m_k}\end{cases}$$其中为正整数且两$a_l,a_2,\cdots,a_k,m_l,m_2,\cdots,m_k$两互质，求最小非负整数解$x$.举例求解以下同余方程组$$\begin{cases}x\equiv l\pmod{2}\\x\equiv2\pmod{3}\\x\equiv3\pmod{5}\end{cases}$$解法由于两两互质，因此可以使用中国剩余定理求$2,3,5$解该同余方程组令则有$M=m_lm_2m_3=2\times3\times5=30$,$$\begin{cases}M_l=15\equiv l\pmod{2}\\M_2=10\equiv2\pmod{3}\\M_3=6\equiv l\pmod{5}\end{cases}$$根据扩展欧几里得算法求出$$\begin{cases}l\times15+0\times10-l\times3=12\\-l\times15+l\times10+0\times3=5\\2\times15-l\times10-l\times6=18\end{cases}$$因此通解为$x\equiv l\times12+2\times5+3\times18\equiv最小非负整数解为89\pmod{30}$,$x=89-30\times3=29$.。