[number theory] congruence (4): univariate linear congruence equations (elimination of two, Chinese remainder theorem)

The congruence problem is 7part, My blog links ：

• Basic concepts and properties
• Inverse element ： Concept 、 Solution method and derivation
• Linear congruence equation
  • Univariate linear congruence equation
  • Univariate Linear Congruence Equations
  • Multivariate linear congruence equation
• Higher order congruence equation ：BSGS Algorithm （ Large and small step algorithm 、 Bashan algorithm ）
• Fast power and fast power of matrix

Univariate Linear Congruence Equations

Form like ：
$$\{\begin{array}{ll}x\equiv a_1& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ x\equiv a_2& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)\\ & ⋮\\ x\equiv a_n& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_n)\end{array}$$

Method 1 ： The two disappear

Let's start with two equations ：
$$\{\begin{array}{l}x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ x\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)\end{array}$$
Turn into
$$\{\begin{array}{l}x+m_1{k}_1=a_1\\ x+m_2{k}_2=a_2\end{array}\text{\hspace{1em}(1)}$$
Then we get $$a_1-m_1{k}_1=a_2-m_2{k}_2$$ namely $$m_1{k}_1-m_2{k}_2=a_1-a_2$$ Then the equivalent condition of a solution is $$\gcd (m_1,m_2)\mid (a_1-a_2)$$ Use the solution of univariate linear congruence equation in the previous section to solve $k_1$ A special solution of $k^{\prime }$ , So the general solution $$k_1=k^{\prime }+\frac{c{m}_2}{\gcd (m_1,m_2)},c\in N$$ Plug in $(1)$ Type available ,$$x=a_1-m_1{k}^{\prime }+\frac{c{m}_1{m}_2}{\gcd (m_1,m_2)}$$ So it is transformed into a new congruence equation ：$$x\equiv a_1-m_1{k}^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}\text{lcm}(m_1,m_2))$$ Merge in turn to get the final answer .

//  solve  x==a[] mod m[], Array from 0 Numbered starting , common n Formulas 
int mod_equations(int a[], int m[], int n)
{
    
    int a1 = a[0], a2, m1 = m[0], m2, k1, k, d;
    for (int i = 1; i < n; i++)
    {
    
        a2 = a[i], m2 = m[i];
        int k2, tmp;
        exgcd(m1, m2, d, k1, k2);
        if ((a2 - a1) % d)
            return -1;
        tmp = m2 / d;
        k1 = (k1 * (a2 - a1) / d % tmp + tmp) % tmp; //  Special solution k', Ensure the minimum positive number 
        a1 += m1 * k1;
        m1 *= m2 / d;
        a1 = (a1 + m1) % m1;
    }
    return a1; //  The general solution is a1+cm1,c Is an integer 
}

Method 2 ： Chinese remainder theorem

Conditions ： Original equations $m_1,m_2\cdots m_n$ Relatively prime

Theorem ： Patterned $M=m_1\cdot m_2\cdots m_n$ The only solution

deduction ： Make $M_i=M/m_i$ , Mutual prime knowledge $\gcd (M_i,m_i)=1$ , also $M_i\cdot M_i^{-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$ , The general solution is $$cM+\sum _{i=1}^n{a}_i{M}_i{M}_i^{-1}$$

//  Chinese remainder definite understanding univariate Linear Congruence Equations , Array from 0 label 
ll CRT(int a[], int m[], int n)
{
    
    ll M = 1ll, ans = 0;
    for (int i = 0; i < n; i++)
        M *= m[i];
    for (int i = 0; i < n; i++)
        ans = (ans + a[i] * M % M * inv(M) % M) % M;
    return ans;
}