Notes congruence


If \ (m \mid a-b \), then \ (a \equiv b \pmod m \)

Important formula: \ ({a \bmod b = a-b\lfloor a/b\rfloor} \)


  • AcWing202: the luckiest number It's hard (worth doing!)
    \Ask how many positive integers composed of at least 8 are multiples of L (\ (L ≤ 2 × 10^9\)​​)
    AC code Note: there is a disadvantage of fast power - it may explode long long, which is needed at this time Turtle speed ride

  • AcWing97: Sumdiv Canon
    \Find the sum of all divisors of \ (A^B \) mod 9901
    AC code

  • Calculator Template (worth doing!)

    \(general idea \) ask \ (a^b\bmod p \), \ (ax\equiv b\pmod p \), \ (a^x\equiv b\pmod p \)

    AC code

  • Desert island Savage Finding congruence without solution

    \(main idea \) find the minimum M so that for any i,j, the following congruence equation has no solution:


    \[ \]

    \(AC code \)

    \(question \) in solving the linear congruence equation:

    int getK(Being o1, Being o2, int m){
    	int a=Mod(o1.P-o2.P, m), b=o2.C-o1.C, m;   //It's strange here (try to swap the two subtraction operands, or add or remove the Mod of a or b...) It seems to be feasible in mathematics, but the algorithm can't solve it
    	int x, y, d=exgcd(a, m, x, y);
    	if(b%d!=0) return -1;
    	return Mod(x*b/d, m/d);


  • Multiplicity: if \ (a\equiv b\pmod m \) and \ (c\equiv d\pmod m \), there is \ (ac\equiv bd\pmod m \)
  • Isomorphism: if \ (a\equiv b\pmod m \), then \ (a^n\equiv b^n\pmod m \)
  • If \ (a\bmod p=x,\ a\bmod q=x \) and p, q are coprime, then \ (a\bmod (pq)=x \)
  • Does not satisfy the identity division

Algorithms and theorems

  • Fermat's theorem: if p is a prime number, there is \ (a^p \equiv a\pmod p \) for any integer a
    (Fermat's small theorem is a special case of Euler's theorem)

  • Euler's theorem: if positive integers a and N are coprime, then \ (a^{\varphi(n)} \equiv 1\pmod n \)
    Inference (can be used to reduce the scale of the index to a range that is easy to calculate):

    1. If the positive integers a and N are coprime, there is \ (a^b \equiv a^{b\bmod \varphi(n)}\pmod n \) for any positive integer b
    2. When a and N are not necessarily coprime, and \ (b > \ varphi (n) \) has \ (a^b \equiv a^{b \bmod \varphi(n)+\varphi(n)}\pmod n \)
    3. If positive integers a and B are coprime, the minimum positive integer satisfying \ (a^x \equiv 1\pmod n \) \ (x_0 \) is the divisor of \ (\ varphi(n) \)
  • Bezout theorem: for any integer a,b, there is a pair of integers x,y, satisfying \ (ax+by=\gcd(a,b) \)
    Given that a,b, X and y satisfy the above formula, it can be used extended euclidean algorithm :

  • Multiplicative inverse: if integers B and m are coprime and \ (b\mid a \), there is an integer x such that \ (a/b \equiv a × x\pmod m \), which is called the multiplicative inverse of B module M and is recorded as \ (b^{-1}\pmod m \)

    • \(b × b^{-1} \equiv 1\pmod m \) the congruence equation is the main formula for solving the multiplicative inverse
    • When m is prime, then \ (b × b^{m-2} \equiv 1\pmod m\)
    • If B and m are not coprime, then \ (bx \equiv 1\pmod m \) has no integer solution, that is, there is no multiplicative inverse
  • Linear congruence equation \ (ax \equiv b\pmod m \) this equation is equivalent to \ (ax+my=b \)

    • Solvable if and only if \ (\ gcd(a,m)\mid b \)
    • solve An algorithm for finding the Euclidean solution of (CD \ \ Gu, x = \\\\\\\\\\ × b/ \gcd(a, m) \) is a solution of the original congruence equation
    • Solution (CD \ {\ gquim})


  • ll exgcd(ll a, ll b, ll &x, ll &y){
    	if(!b){ x=1, y=0; return a; }
    	ll d=exgcd(b, a%b, x, y);
    	ll t=x; x=y; y=t-y*(a/b);  // Key points (this formula comes from the proof of Bezout theorem)
    	return d;
  • Solve \ (ax\equiv b\pmod p \)

    inline ll Mod(ll a, ll b){ return (a%b+b)%b; }	// a is the smallest positive integer with modulus b
    ll solve(ll a, ll b, ll p){
    	ll x, y, d=exgcd(a, p, x, y);
    	if(b%d!=0) return -1;	// unsolvable
    	return Mod(x*b/d, abs(p/d));	// Note that the modulus here is p/d, not P, 

    In some topics, such as Desert island Savage , d may be negative, so abs is needed
    In addition, don't mod (a, P) or mod (B, P) at the beginning I don't know the reason. The question of "desert island savage" will inexplicably WA

  • Solving Linear Congruence Equations


    x\equiv a_1\pmod {m_1} \
    x\equiv a_2\pmod {m_2} \
    ... \
    x\equiv a_n\pmod {m_n}

    \[ \]

      ll res=0;
      REP(i, 1, n) M*=m[i];
      REP(i, 1, n){
          ll Mi=M/m[i], x, y;
          exgcd(Mi, m[i], x, y);
          res=Mod(res+A[i]*Mi*x%M, M);	// The multiplication of three numbers here may explode long long, which can be multiplied at turtle speed
      printf("%lld\n", Mod(res, M);
    1. When \ (m \) does not guarantee mutual prime, it can be obtained by extended Euclidean algorithm + mathematical induction recursion Examples
      ll solve(){
          ll M=1, o=0;
          REP(i, 1, n){
              if(!(M%mo[i]) && x0%mo[i]==A[i]) continue;  // accelerate
              ll x, y, b=Mod(A[i]-o, m[i]);
              ll d=exgcd(M, m[i], x, y);
              if(b%d!=0) return -1;
                 x=smul(x, b/d, m[i]/d);	// Multiplication is an abomination because it explodes easily
              ll t=M; M=M/d*m[i];	// M = lcm{m}
              o=Mod(o+smul(x, t, M), M);	// Turtle speed ride
          return o;
  • Minimum positive integer solution of \ (a^x\equiv b\pmod p \) for solving high-order congruence equation (Baby Setp, Giant Setp algorithm)

    map<ll, int> h;
    ll solve_3(ll a, ll b, ll p){
    h.clear(); a%=p, b%=p;  // Mold it first This sentence can't be saved!
    ll sp=ceil(sqrt(1.0*p));
    FOR(j, 0, sp){
    	ll t=b*qpow(a, j, p)%p;
    a=qpow(a, sp, p);
    if(a==0) return b==0 ?1 :-1;    // Cannot return 0!
    REP(i, 0, sp){
    	ll t=qpow(a, i, p);
    	int j=(h.count(t) ?h[t] :-1);
          if(j>=0 && i*sp-j>=0) return i*sp-j;
    return -1;

Keywords: Math

Added by DontheCat on Tue, 08 Mar 2022 03:22:18 +0200