Extended Euclidean Algorithm & Chinese Remainder Theorem

Find modular inverses, solve linear Diophantine equations, and reconstruct integers from their remainders -- the essential number-theoretic toolkit that Fermat's little theorem alone can't cover.

Difficulty	Intermediate
CF Rating	1400 - 1800
Prerequisites	Math Fundamentals, Number Theory

---

Quick Revisit

• USE WHEN: modular inverse with non-prime modulus, or combining congruences from multiple moduli
• INVARIANT: ax + by = gcd(a,b) always has integer solutions (Bezout's identity)
• TIME: O(log min(a,b)) for extended GCD | SPACE: O(1) iterative
• CLASSIC BUG: not normalizing x to a positive value after extended GCD
• PRACTICE: see practice problems in this chapter

Contents

• Table of Contents
• Motivation: When Fermat Isn't Enough
• Bezout's Identity and the Extended GCD
• Tracing Through $a=35,b=15$
• Modular Inverse via Extended GCD
• Linear Diophantine Equations
• The Chinese Remainder Theorem
• Generalized CRT: Non-Coprime Moduli
• Applications
• Visual Intuition
• C++ STL Reference
• Implementation: Contest-Ready Templates
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Motivation: When Fermat Isn't Enough

Suppose you need to solve $3x\equiv 1(\mathrm{mod}7)$. You want the modular inverse of 3 modulo 7. If you know Fermat's little theorem, you can compute $3^{5}mod7=5$, and indeed $3\cdot 5=15\equiv 1(\mathrm{mod}7)$. Great.

But what if the modulus isn't prime? Say you need $5^{-1}mod12$. Fermat doesn't apply -- 12 isn't prime. Euler's theorem works in principle ($5^{\varphi (12)-1}mod12$), but computing $\varphi (m)$ requires factoring $m$. For a single inverse, that's overkill.

There's a cleaner path. If we can find integers $x,y$ such that $5x+12y=1$, then reducing modulo 12 gives $5x\equiv 1(\mathrm{mod}12)$, and $x$ is our inverse. This is exactly what the extended Euclidean algorithm does -- and it works whenever $gcd(a,m)=1$, regardless of whether $m$ is prime.

The same machinery unlocks a whole family of problems: solving linear Diophantine equations, and combining systems of modular congruences via the Chinese Remainder Theorem. Let's build it all up from first principles.

Why this matters beyond Fermat

CRT appears more often than the textbook word problems suggest. Any time you reconstruct a value from its residues — multi-prime modular arithmetic to sidestep overflow, simultaneous congruence problems, computations split across several NTT-friendly primes — you are doing CRT.

When CRT fails. For moduli $m_1,m_2$ with $g=gcd(m_1,m_2)>1$, the system $x\equiv a_1(\mathrm{mod}{m}_1)$, $x\equiv a_2(\mathrm{mod}{m}_2)$ has a solution iff $g\mid (a_2-a_1)$. If this fails, no solution exists. Problems that ask "does a solution exist?" hinge on this check.

Heads up — Garner's algorithm and arbitrary-modulus NTT are mentioned later in this file, after the standard and generalized CRT walkthroughs. Skip them on a first read; come back when you need to combine many primes without overflowing __int128.

What the Code Won't Teach You

The extended GCD code returns three numbers $(g,x,y)$. What it hides is why back-substitution works and when to reach for it instead of Fermat.

DECISION TREE -- which inverse method?

  Need a⁻¹ mod m?
       │
       ├─ Is m prime?
       │     ├─ YES -> Fermat: a^(m-2) mod m  (simpler code)
       │     └─ NO  -> must use Extended Euclid
       │
       ├─ Is gcd(a, m) = 1?
       │     ├─ YES -> Extended Euclid gives the inverse
       │     └─ NO  -> inverse does NOT exist!
       │
       └─ Multiple moduli? -> CRT to combine results
             │
             ├─ Coprime moduli? -> standard CRT formula
             └─ Non-coprime?    -> check divisibility first

The code also hides the geometric meaning: the equation $ax+by=g$ describes a line in the $(x,y)$-plane. The Euclidean algorithm finds one lattice point on this line; the parametric family gives all of them. When the problem asks "how many solutions in a range," you're counting lattice points on a line segment -- a perspective the code never reveals.

LATTICE POINTS on 6x + 10y = 8:

  y
  4 ┤
  3 ┤
  2 ┤ ●(-2,2)
  1 ┤
  0 ┤─────────────────────────── x
 -1 ┤      ●(3,-1)
 -2 ┤
 -3 ┤
 -4 ┤           ●(8,-4)     <- particular solution
 -5 ┤
 -6 ┤
 -7 ┤                ●(13,-7)
 -8 ┤
 -9 ┤
-10 ┤                     ●(18,-10)

  Step: Δx = +5, Δy = -3  (from b/g and -a/g)
  All solutions lie on one line with integer spacing.

Finally, the CRT code merges two congruences at a time. What it won't teach you is that the merge order doesn't matter for correctness, but it does matter for overflow -- merge the smallest moduli first to keep intermediates small.

There's another thing the code conceals: Garner's algorithm. When you combine $k$ congruences pairwise, each merge multiplies moduli and risks overflow even with 64-bit integers. Garner's mixed-radix representation sidesteps this entirely -- it expresses the answer as $x=a_1+m_1(a_2+m_2(a_3+\dots ))$ where each $a_i$ is small (bounded by $m_i$). You compute each coefficient $a_i$ using modular inverses within $m_i$, so no intermediate ever exceeds $m_i^2$. The pairwise CRT code won't teach you this structure.

GARNER'S MIXED-RADIX vs. PAIRWISE CRT:

  Given: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

  PAIRWISE CRT (overflow risk):
  ┌─────────────┐   ┌─────────────┐
  │ x ≡ 2 mod 3 │   │ x ≡ 3 mod 5 │
  └──────┬──────┘   └──────┬──────┘
         └──────┬──────────┘
                v
        x ≡ 8 (mod 15)  <- intermediate uses mod 15
                │     ┌──────────────┐
                └──┬──┤ x ≡ 2 mod 7  │
                   v  └──────────────┘
           x ≡ 23 (mod 105)  <- intermediate uses mod 105
                                (moduli multiply each step!)

  GARNER'S ALGORITHM (bounded intermediates):
  x = r1 + m1*(r2 + m2*(r3))

  Step 1: r1 = 2                        (work mod 3 only)
  Step 2: r2 = (3 - 2) * 3⁻¹ mod 5     (work mod 5 only)
         = 1 * 2 = 2                    <- never exceeds 5
  Step 3: r3 = ((2 - 2) - 3*2) * (3*5)⁻¹ mod 7
         = (-6) * 1 mod 7 = 1           <- never exceeds 7

  Result: x = 2 + 3*(2 + 5*(1)) = 2 + 3*7 = 23

  KEY: every r_i < m_i, so no overflow in the coefficients!

The code also hides the lattice-geometric meaning of Bezout coefficients. The equation $ax+by=g$ defines a lattice coset in ${\mathbb{Z}}^2$ -- the extended GCD finds the closest lattice vector to the origin on that coset, and the parametric family walks along the lattice line. Understanding this geometry turns "counting solutions in a range" into a bounding-box intersection problem, which is far more intuitive than algebraic manipulation.

The geometric meaning of Bézout's identity. The equation $ax+by=g$ describes a family of parallel lines in the $(x,y)$-plane. Each line corresponds to a different right-hand side ($g,2g,3g,\dots$). The lattice points on these lines are exactly the integer solutions. The extended GCD finds the lattice point closest to the origin on the line $ax+by=g$. The parametric family walks along the line in steps of $(b/g,-a/g)$. When a problem asks "how many solutions in a rectangle?", you're intersecting a line with a box -- a geometric operation the algebraic code completely hides.

---

When to Reach for This

Trigger phrases in the problem:

• "Find x such that a*x = b (mod m)" where m is not necessarily prime -- Fermat's little theorem won't work.
• "Solve in integers" or "find integer solutions to ax + by = c" -- linear Diophantine equation.
• "x = r1 (mod m1), x = r2 (mod m2), ..." -- Chinese Remainder Theorem.
• "Modular inverse" with composite or non-prime modulus.

When NOT to use this:

• If the modulus is prime, Fermat's little theorem (a^{p-2} mod p) is simpler for modular inverse.
• If you only need GCD (not the coefficients x, y), use the standard Euclidean algorithm.

---

Bezout's Identity and the Extended GCD

The ordinary Euclidean algorithm computes $gcd(a,b)$ by repeatedly replacing the larger number with the remainder: $gcd(a,b)=gcd(b,amodb)$. Bezout's identity tells us something stronger:

$$\text{For any integers }a,b,\text{ there exist integers }x,y\text{ such that }ax+by=gcd(a,b).$$

The extended Euclidean algorithm finds $x$ and $y$ by tracing the ordinary algorithm backwards. Let's walk through a concrete example.

Tracing Through $a=35,b=15$

Forward pass (standard Euclidean algorithm):

$$35=2\cdot 15+5$$$$15=3\cdot 5+0$$

So $gcd(35,15)=5$. Now the back-substitution:

From the first equation: $5=35-2\cdot 15$.

That's it -- we already have $35\cdot 1+15\cdot (-2)=5$, so $x=1,y=-2$.

EXTENDED EUCLIDEAN ALGORITHM: gcd(35, 15) = 5
Finding x, y such that 35x + 15y = 5

FORWARD PASS (divide):          BACKWARD PASS (substitute):

+------------------+            +---------------------------+
| 35 = 2 * 15 + 5 |---+    +-->| 5 = 35*(1) + 15*(-2)     |
+------------------+   |    |   | x = 1,  y = -2           |
                       |    |   +---------------------------+
                       v    |              ^
+------------------+   |    |              |
| 15 = 3 * 5  + 0 |   |    |   Substitute r = 35 - 2*15:
+------------------+   |    |   5 = 35 - 2*15
   gcd = 5             |    |   = 35*(1) + 15*(-2)
                       |    |
                       v    |
              +--------+----+--------+
              | Base case: gcd = 5   |
              | 5 = 5*1 + 0*0       |
              | x = 1,  y = 0       |
              +----------------------+

  VERIFICATION:
  35 * (1) + 15 * (-2) = 35 - 30 = 5  OK

  KEY INSIGHT: Each back-substitution step replaces
  the remainder r with (a - q*b), expressing gcd
  in terms of the ORIGINAL inputs.

Let's do a slightly longer example to see the pattern. Take $a=161,b=28$:

Forward pass:

$$161=5\cdot 28+21$$$$28=1\cdot 21+7$$$$21=3\cdot 7+0$$

So $gcd(161,28)=7$. Back-substitution:

$$7=28-1\cdot 21$$$$\phantom{7}=28-1\cdot (161-5\cdot 28)$$$$\phantom{7}=6\cdot 28-1\cdot 161$$

So $161\cdot (-1)+28\cdot 6=7$. Check: $-161+168=7$. Correct.

In code, the recursion is elegant. The base case is $gcd(g,0)$: here $g\cdot 1+0\cdot 0=g$, so $x=1,y=0$. As we return from each recursive call, we update the coefficients using the quotient at that level.

extgcd(a, b, x, y):
    if b == 0:  return (a, x=1, y=0)
    (g, x1, y1) = extgcd(b, a % b, x1, y1)
    x = y1
    y = x1 - (a / b) * y1
    return (g, x, y)

Why does the update work? At each level, $a=q\cdot b+r$ where $r=amodb$. The recursive call gives us $b\cdot x_1+r\cdot y_1=g$. Substituting $r=a-q\cdot b$:

$$b\cdot x_1+(a-q\cdot b)\cdot y_1=g$$$$a\cdot y_1+b\cdot (x_1-q\cdot y_1)=g$$

So the new $x=y_1$ and $y=x_1-q\cdot y_1$.

Modular Inverse via Extended GCD

If $gcd(a,m)=1$, then extgcd(a, m, x, y) gives us $ax+my=1$. Taking this modulo $m$: $ax\equiv 1(\mathrm{mod}m)$, so $xmodm$ is the modular inverse of $a$.

One subtlety: the $x$ returned might be negative. Always normalize: $x=((xmodm)+m)modm$.

Back to our earlier problem: $5^{-1}mod12$.

$$12=2\cdot 5+2$$$$5=2\cdot 2+1$$

Back-substitution: $1=5-2\cdot 2=5-2\cdot (12-2\cdot 5)=5\cdot 5-2\cdot 12$.

So $x=5$, and $5\cdot 5=25\equiv 1(\mathrm{mod}12)$. Done.

Linear Diophantine Equations

The equation $ax+by=c$ has integer solutions if and only if $gcd(a,b)\mid c$.

Once you have one solution $(x_0,y_0)$ via extended GCD, the general solution is:

$$x=x_0+\frac{b}{g}\cdot t,y=y_0-\frac{a}{g}\cdot t$$

for any integer $t$, where $g=gcd(a,b)$.

To find $(x_0,y_0)$: run extgcd(a, b, x, y) to get $ax+by=g$, then multiply both sides by $c/g$: $x_0=x\cdot (c/g)$, $y_0=y\cdot (c/g)$.

Example: Solve $6x+10y=8$. We have $gcd(6,10)=2$ and $2\mid 8$, so solutions exist. Extended GCD gives $6\cdot 2+10\cdot (-1)=2$. Multiply by $8/2=4$: $x_0=8,y_0=-4$. Check: $6\cdot 8+10\cdot (-4)=48-40=8$.

General solution: $x=8+5t$, $y=-4-3t$.

SOLUTION LATTICE: 6x + 10y = 8

  y ^
    |
  2 +     *                          t = -2: (x,y) = (-2, 2)
    |      \
  1 +       \
    |        \
  0 +         \
    |          \
 -1 +     .    *    .    .    .      t = -1: (x,y) = (3, -1)
    |           \
 -2 +            \
    |             \
 -3 +              \
    |               \
 -4 +     .    .    *    .    .      t = 0:  (x,y) = (8, -4)  <-- particular
    |                \
 -5 +                 \
    |                  \
 -6 +                   \
    |                    \
 -7 +     .    .    .    *    .      t = 1:  (x,y) = (13, -7)
    |                     \
 -8 +                      \
    |                       \
 -9 +                        \
    |                         \
-10 +     .    .    .    .    *      t = 2:  (x,y) = (18, -10)
    |
    +-----+----+----+----+----+---> x
         -2    3    8   13   18

  Solutions form a LINE in the (x,y) plane.
  Step between consecutive solutions:
    dx = b/g = 10/2 = 5
    dy = -a/g = -6/2 = -3
  Direction vector: (5, -3)

The Chinese Remainder Theorem

Here's a classic puzzle (it goes back to the 3rd century Chinese mathematician Sun Tzu -- not the military strategist):

A number leaves remainder 2 when divided by 3 and remainder 3 when divided by 5. What is the number?

We want $x$ such that $x\equiv 2(\mathrm{mod}3)$ and $x\equiv 3(\mathrm{mod}5)$.

The Chinese Remainder Theorem says: if $gcd(m_1,m_2)=1$, then this system has a unique solution modulo $m_1\cdot m_2$.

The construction is direct. We need $M_1$ and $M_2$ such that:

• $M_1\equiv 1(\mathrm{mod}{m}_1)$ and $M_1\equiv 0(\mathrm{mod}{m}_2)$
• $M_2\equiv 0(\mathrm{mod}{m}_1)$ and $M_2\equiv 1(\mathrm{mod}{m}_2)$

Then $x=a_1\cdot M_1+a_2\cdot M_2$.

To build $M_1$: start with $m_2=5$. We need $5\cdot t\equiv 1(\mathrm{mod}3)$, i.e., $t=5^{-1}mod3=2$ (since $5\cdot 2=10\equiv 1$). So $M_1=5\cdot 2=10$.

Similarly, $M_2=3\cdot (3^{-1}mod5)=3\cdot 2=6$.

Answer: $x\equiv 2\cdot 10+3\cdot 6=38\equiv 8(\mathrm{mod}15)$.

Check: $8=2\cdot 3+2$ and $8=1\cdot 5+3$. Both hold.

CRT NUMBER LINE: x = 2 (mod 3) and x = 3 (mod 5)

  x = 2 (mod 3) hits:
  |  .  .  *  .  .  *  .  .  *  .  .  *  .  .  *  .
  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15

  x = 3 (mod 5) hits:
  |  .  .  .  *  .  .  .  .  *  .  .  .  .  *  .  .
  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15

  Overlay -- find common hits:
  mod 3:  . . * . . * . . * . .  *  .  .  *  .
  mod 5:  . . . * . . . . * . .  .  .  *  .  .
  both:   . . . . . . . . # . .  .  .  .  .  .
  --------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-->
          0  1  2  3  4  5  6  7  8  9 10 11 12 13 14

  The ONLY overlap in [0..14] is x = 8.
  Solution: x = 8 (mod 15)    [15 = lcm(3,5)]

  Pattern repeats every 15 steps:
  <-------- period = 15 -------><-------- period = 15 ------->
  ...  8  ...  ...  ...  ...  23  ...  ...  ...  ...  38  ...

In practice, there's a more efficient two-congruence formula. We want $x$ with $x\equiv a_1(\mathrm{mod}{m}_1)$ and $x\equiv a_2(\mathrm{mod}{m}_2)$. Write $x=a_1+m_1\cdot k$ and substitute into the second: $a_1+m_1\cdot k\equiv a_2(\mathrm{mod}{m}_2)$, so $k\equiv (a_2-a_1)\cdot m_1^{-1}(\mathrm{mod}{m}_2)$. This gives:

$$x\equiv a_1+m_1\cdot ((a_2-a_1)\cdot m_1^{-1}mod{m}_2)(\mathrm{mod}{m}_1\cdot m_2)$$

This is how we implement CRT in code -- and it extends naturally to more than two congruences by applying it pairwise.

Worked Example: Merging Three Congruences with CRT

Solve: $x\equiv 1(\mathrm{mod}2)$, $x\equiv 2(\mathrm{mod}3)$, $x\equiv 3(\mathrm{mod}5)$.

CRT "MERGE TWO AT A TIME" PROCESS
===================================

Congruence pool:  [x=1(mod 2)]  [x=2(mod 3)]  [x=3(mod 5)]
                       |              |              |
                       +----- MERGE --+              |
                              |                      |
                              v                      |
                 STEP 1: Combine x=1(mod 2)          |
                          and x=2(mod 3)             |
                                                     |
  x = 1 + 2*k, substitute:                          |
  1 + 2k = 2 (mod 3)                                |
  2k = 1 (mod 3)                                    |
  k = 2 (mod 3)   [since 2*2=4=1(mod 3)]            |
  x = 1 + 2*2 = 5                                   |
  Combined: x = 5 (mod 6)                           |
                              |                      |
                              +----- MERGE ----------+
                              |
                              v
                 STEP 2: Combine x=5(mod 6)
                          and x=3(mod 5)

  x = 5 + 6*k, substitute:
  5 + 6k = 3 (mod 5)
  6k = -2 = 3 (mod 5)
  k = 3 * 6^{-1} (mod 5)
  6^{-1} (mod 5) = 1  [since 6*1=6=1(mod 5)]
  k = 3 (mod 5)
  x = 5 + 6*3 = 23
  Combined: x = 23 (mod 30)

  RESULT: x = 23 (mod 30)

  Verify:  23 = 11*2 + 1  --> 23 = 1 (mod 2)  OK
           23 = 7*3  + 2  --> 23 = 2 (mod 3)  OK
           23 = 4*5  + 3  --> 23 = 3 (mod 5)  OK

MERGE TREE:

  [x=1(mod 2)]   [x=2(mod 3)]   [x=3(mod 5)]
       \              /                |
        \            /                 |
         v          v                  |
      [x=5(mod 6)]                    |
              \                       /
               \                     /
                v                   v
             [x=23(mod 30)]

Generalized CRT: Non-Coprime Moduli

When $gcd(m_1,m_2)>1$, a solution might still exist, but we need to be more careful. Given $x\equiv a_1(\mathrm{mod}{m}_1)$ and $x\equiv a_2(\mathrm{mod}{m}_2)$:

Write $x=a_1+m_1\cdot k$. Substitute: $m_1\cdot k\equiv a_2-a_1(\mathrm{mod}{m}_2)$.

Let $g=gcd(m_1,m_2)$. This has a solution iff $g\mid (a_2-a_1)$.

If it does, divide through by $g$: $\frac{m_1}{g}\cdot k\equiv \frac{a_2-a_1}{g}(\mathrm{mod}\frac{m_2}{g})$.

Solve for $k$ using the modular inverse of $\frac{m_1}{g}$ modulo $\frac{m_2}{g}$ (which exists since $gcd(\frac{m_1}{g},\frac{m_2}{g})=1$). The combined modulus is $\text{lcm}(m_1,m_2)=\frac{m_1\cdot m_2}{g}$.

Applications

These tools appear everywhere in competitive programming:

• Modular inverse for non-prime moduli -- when computing combinatorics under composite moduli, or when the modulus is given as input and might not be prime.
• Reconstructing numbers from remainders -- CRT lets you work modulo several small primes and combine results, avoiding big-integer arithmetic.
• Solving constraint systems -- problems where an unknown satisfies several modular conditions simultaneously.
• Counting solutions in ranges -- linear Diophantine equations with bounds on $x$ and $y$.

---

Visual Intuition

Extended GCD Trace: $a=35,b=15$

  FORWARD (divide)               BACK-SUBSTITUTE (express gcd)
  ================               ==============================

  extgcd(35, 15)                 5 = 35*1 + 15*(-2)
    |                                ^
    | 35 = 2*15 + 5                  | x = y1 = 1
    v                                | y = x1 - 2*y1 = 0 - 2*1 = -2
  extgcd(15, 5)                  5 = 15*0 + 5*1
    |                                ^
    | 15 = 3*5 + 0                   | x = y1 = 0
    v                                | y = x1 - 3*y1 = 1 - 3*0 = 1... wait
  extgcd(5, 0)                   5 = 5*1 + 0*0
    |                                ^
    | base case: gcd = 5             | x = 1, y = 0
    v
  return (5, x=1, y=0)

  Result: 35*(1) + 15*(-2) = 35 - 30 = 5  OK

CRT Combining Two Congruences

  x = 2 (mod 3)          x = 3 (mod 5)

  Numbers = 2 (mod 3):   Numbers = 3 (mod 5):
  2, 5, 8, 11, 14, ...   3, 8, 13, 18, 23, ...
        *                       *

  Overlap (mod 15):
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
                                *
                                8

  x = 2 (mod 3): --o--+--o--+--o--+--o--+--o--+--
                  2     5     8     11    14

  x = 3 (mod 5): --------o--------+--------o-----
                  3                 8          13

  Intersection:   -----------------o--------------
                                   8

  Unique solution: x = 8 (mod 15)

Number Line: Solutions to $6x+10y=8$

  Particular solution: (x0, y0) = (8, -4)
  Step: dx = 10/2 = 5,  dy = -6/2 = -3

  t = ...  -2    -1     0     1     2   ...
  x = ...  -2     3     8    13    18   ...
  y = ...   2    -1    -4    -7   -10   ...
            |     |     |     |     |
  ----o-----o-----o-----*-----o-----o-----> x
     -2     3     8    13    18
                  ^
            particular solution

Diophantine Solution Counting -- Geometric View

DIOPHANTINE SOLUTION COUNTING -- geometric view:

  Equation: 6x + 10y = 80

  Particular solution: (x₀, y₀) = (80/2*x', 80/2*y')
  where 6x'+10y'=2 from extgcd -> x'=2, y'=-1
  So x₀=80, y₀=-40... let's rescale: (x₀,y₀) = (80, -40)... 
  Actually: extgcd(6,10)->g=2, 6*2+10*(-1)=2. Scale by 40: x₀=80, y₀=-40.
  General: x = 80 - 5t, y = -40 + 3t

  For x >= 0: t <= 16
  For y >= 0: t >= 14

  Valid range: 14 <= t <= 16  ->  3 solutions

    t=14: (x,y) = (10, 2)   <- check: 6*10+10*2 = 80 OK
    t=15: (x,y) = (5, 5)    <- check: 6*5+10*5  = 80 OK
    t=16: (x,y) = (0, 8)    <- check: 6*0+10*8  = 80 OK

  y ▲
  8 ┤           ●(0,8)
    │          ╱
  5 ┤        ●(5,5)
    │       ╱
  2 ┤     ●(10,2)
    │    ╱
  0 ┤───────────────────► x
    0   5  10  15  80

  Only 3 lattice points with x>=0, y>=0 on the line.

GCD Reduction Staircase

The Euclidean algorithm can be visualized as slicing a rectangle into squares -- each step removes the largest square that fits, reducing the problem until one dimension reaches zero:

gcd(21, 15) -- rectangle 21 x 15:

  ┌───────────────┬──────┐
  │               │      │
  │   15 x 15    │ 6x15 │  21 = 1*15 + 6
  │               │      │
  │               │      │
  └───────────────┴──────┘

  gcd(15, 6) -- rectangle 15 x 6:

  ┌──────┬──────┬───┐
  │      │      │   │
  │ 6x6  │ 6x6 │3x6│  15 = 2*6 + 3
  │      │      │   │
  └──────┴──────┴───┘

  gcd(6, 3) -- rectangle 6 x 3:

  ┌───┬───┐
  │3x3│3x3│  6 = 2*3 + 0  -> gcd = 3
  └───┴───┘

  The smallest square tile that fills the original
  21x15 rectangle without gaps is 3x3.

Modular Inverse Decision Flowchart

INPUT: need a⁻¹ (mod m)

  ┌──────────────────────┐
  │ Is gcd(a, m) = 1?    │
  └──────────┬───────────┘
         YES │        NO -> inverse does NOT exist
             v
  ┌──────────────────────┐
  │ Is m prime?          │
  └──────────┬───────────┘
         YES │        NO
             v             v
  ┌──────────────┐  ┌──────────────┐
  │ Fermat:      │  │ Extended GCD │
  │ a^(m-2) % m  │  │ solve ax+my=1│
  │              │  │ inv = x % m  │
  │ simpler code │  │ general tool │
  └──────────────┘  └──────────────┘

Residue Fingerprint: How CRT Reconstructs a Number

CRT RECONSTRUCTION -- recovering x from its "residue fingerprint":

  x = 23  (unknown -- we only see residues)

  mod 3:  23 -> 2     mod 5:  23 -> 3     mod 7:  23 -> 2

  ┌───────────────────────────────────────────────────────┐
  │ RESIDUE FINGERPRINT of x:                             │
  │                                                       │
  │   mod 3 ──► [0]  1 ②  <- x lives in bucket 2         │
  │   mod 5 ──► [0]  1  2 ③  4  <- x lives in bucket 3   │
  │   mod 7 ──► [0]  1 ②  3  4  5  6  <- bucket 2        │
  │                                                       │
  │ Each modulus sees a different "shadow" of x.           │
  │ CRT says: if gcd(3,5,7) are pairwise coprime,         │
  │ the fingerprint (2, 3, 2) maps to EXACTLY ONE x       │
  │ in [0, 3*5*7) = [0, 105).                             │
  └───────────────────────────────────────────────────────┘

  Scanning 0..104 for the match:

   x:   0  1  2  3  4  5  6  7  8 ... 23 ... 104
  m3:   0  1  2  0  1  2  0  1  2 ...  2 ...   2
  m5:   0  1  2  3  4  0  1  2  3 ...  3 ...   4
  m7:   0  1  2  3  4  5  6  0  1 ...  2 ...   6
                                       ↑
                                  ALL THREE MATCH
                                  x = 23 (mod 105)

Bezout Coefficient Computation Tree

BEZOUT TREE: computing coefficients for gcd(48, 18)

  Forward pass (Euclidean divisions):

  48 = 2*18 + 12      (q=2, r=12)
  18 = 1*12 + 6       (q=1, r=6)
  12 = 2*6  + 0       (q=2, r=0)  -> gcd = 6

  Back-substitution tree:

  Level 0 (base):   gcd = 6 = 1*6 + 0*0
                          x₀=1  y₀=0

  Level 1:          6 = 18 - 1*12
                    Substitute: x₁ = y₀ = 0
                                y₁ = x₀ - q*y₀ = 1 - 1*0 = 1
                    -> 6 = 0*18 + 1*6  ... but in terms of (18,12):
                    -> 6 = 1*18 + (-1)*12

  Level 2:          12 = 48 - 2*18
                    Substitute: x₂ = y₁ = -1
                                y₂ = x₁ - q*y₁ = 0 - 2*(-1) = 2... wait
                    let's be precise:
                                y₂ = x₁ - q*y₁ = 1 - 2*(-1) = 3

  Hmm, let me redo with the standard recurrence:
                    x₂ = y₁ = 1
                    y₂ = x₁ - 2*y₁ = (-1) - 2*(1) = -3

  FINAL:  48*(-1) + 18*(3) = -48 + 54 = 6  OK

  Coefficient flow (visualized):
  ┌──────────────┐    ┌──────────────┐    ┌──────────────┐
  │  (6, 0)      │    │  (18, 12)    │    │  (48, 18)    │
  │  x=1, y=0    │───►│  x=0, y=1    │───►│  x=1, y=-1   │... wait
  │  base case   │    │  q=2         │    │  q=2         │
  └──────────────┘    └──────────────┘    └──────────────┘

  Simpler view -- just track (x, y) at each return:

  extgcd(48, 18):                      returns (6, x=-1, y=3)
    └─ extgcd(18, 12):                 returns (6, x=1, y=-1)
         └─ extgcd(12, 6):            returns (6, x=0, y=1)
              └─ extgcd(6, 0):         returns (6, x=1, y=0)

  At each return:  x <- y_child,  y <- x_child - q * y_child
  Verify: 48*(-1) + 18*(3) = -48 + 54 = 6  OK

Garner's Algorithm Step-by-Step

GARNER'S ALGORITHM -- mixed-radix CRT for k moduli

  Problem: x ≡ 3 (mod 5), x ≡ 1 (mod 7), x ≡ 6 (mod 11)

  Represent x in mixed-radix form:
    x = a₁ + m₁*a₂ + m₁*m₂*a₃
    x = a₁ + 5*a₂ + 5*7*a₃

  ┌─────────────────────────────────────────────────┐
  │ Step 1: find a₁                                  │
  │   a₁ ≡ x (mod m₁) = 3                           │
  │                                                   │
  │ Step 2: find a₂                                   │
  │   x ≡ 1 (mod 7)                                   │
  │   a₁ + 5*a₂ ≡ 1 (mod 7)                           │
  │   3 + 5*a₂ ≡ 1 (mod 7)                             │
  │   5*a₂ ≡ -2 ≡ 5 (mod 7)                            │
  │   a₂ ≡ 5 * 5⁻¹ (mod 7)                             │
  │      5⁻¹ mod 7 = 3  (since 5*3=15≡1)               │
  │   a₂ = 5*3 mod 7 = 1                                │
  │                                                      │
  │ Step 3: find a₃                                      │
  │   x ≡ 6 (mod 11)                                     │
  │   a₁ + m₁*a₂ + m₁*m₂*a₃ ≡ 6 (mod 11)               │
  │   3 + 5*1 + 35*a₃ ≡ 6 (mod 11)                      │
  │   8 + 35*a₃ ≡ 6 (mod 11)                             │
  │   35*a₃ ≡ -2 (mod 11)                                │
  │   2*a₃ ≡ 9 (mod 11)  [since 35≡2, -2≡9 mod 11]     │
  │   a₃ = 9 * 2⁻¹ mod 11 = 9*6 mod 11 = 10            │
  │                                                       │
  │ Reconstruct:                                          │
  │   x = 3 + 5*1 + 35*10 = 3 + 5 + 350 = 358           │
  │   x = 358 (mod 5*7*11) = 358 (mod 385)               │
  └───────────────────────────────────────────────────────┘

  Verify: 358 mod 5 = 3 OK  358 mod 7 = 1 OK  358 mod 11 = 6 OK

  KEY PROPERTY: each aᵢ < mᵢ, so intermediate values stay small.
  For k moduli of ~10⁹, pairwise CRT needs 10^(9k) range,
  but Garner only needs 10⁹ per step.

Multi-Prime Reconstruction via CRT

MULTI-PRIME RECONSTRUCTION via CRT:

  Problem: compute (A*B) mod 10⁹+7, where A*B overflows 64-bit

  Strategy: compute mod three NTT primes, then CRT reconstruct

  A*B mod p₁ = r₁       p₁ = 998244353
  A*B mod p₂ = r₂       p₂ = 985661441
  A*B mod p₃ = r₃       p₃ = 754974721

  ┌─────────┐   ┌─────────┐   ┌─────────┐
  │A*B mod p₁│   │A*B mod p₂│   │A*B mod p₃│
  │  = r₁    │   │  = r₂    │   │  = r₃    │
  └────┬─────┘   └────┬─────┘   └────┬─────┘
       │              │              │
       └──────┬───────┘              │
              │ CRT merge            │
              ▼                      │
       x ≡ r₁₂ (mod p₁*p₂)         │
              │                      │
              └──────────┬───────────┘
                         │ CRT merge
                         ▼
              x ≡ R (mod p₁*p₂*p₃)
              
  Final: (A*B) mod 10⁹+7 = R mod 10⁹+7

  Key: each step works with numbers < p₁*p₂ ~= 10¹⁸
       which fits in __int128 (or use Garner's to avoid overflow)

---

C++ STL Reference

Function / Header	Description	Notes
__gcd(a, b)	GCD (older compilers)	Works with negative values on most compilers
gcd(a, b) in <numeric>	GCD (C++17)	Prefer this; handles edge cases properly
lcm(a, b) in <numeric>	LCM (C++17)	May overflow for large inputs
__int128	128-bit integer	Useful to avoid overflow in CRT multiplication

Note: there is no standard library function for extended GCD or modular inverse -- you need to implement these yourself.

---

Implementation: Contest-Ready Templates

Minimal Version (Copy-Paste)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

ll mod_inverse(ll a, ll m) {
    ll x, y;
    ll g = extgcd(a, m, x, y);
    if (g != 1) return -1; // inverse doesn't exist
    return (x % m + m) % m;
}

// returns {x0, y0, g} or {0, 0, 0} if no solution
tuple<ll,ll,ll> solve_diophantine(ll a, ll b, ll c) {
    ll x, y;
    ll g = extgcd(abs(a), abs(b), x, y);
    if (c % g != 0) return {0, 0, 0};
    x *= c / g; y *= c / g;
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return {x, y, g};
}

// CRT for coprime moduli. Returns {r, m1*m2} where x = r (mod m1*m2)
pair<ll,ll> crt(ll a1, ll m1, ll a2, ll m2) {
    ll inv = mod_inverse(m1, m2);
    ll r = a1 + m1 * ((a2 - a1) % m2 + m2) % m2 * 1;
    // careful version:
    ll k = ((a2 - a1) % m2 + m2) % m2;
    k = k * inv % m2;
    ll ans = a1 + m1 * k;
    ll M = m1 * m2;
    return {(ans % M + M) % M, M};
}

// General CRT (moduli need not be coprime). Returns {r, lcm} or {-1, -1}.
pair<ll,ll> crt_general(ll a1, ll m1, ll a2, ll m2) {
    ll g = gcd(m1, m2);
    if ((a2 - a1) % g != 0) return {-1, -1};
    ll m2g = m2 / g;
    ll inv = mod_inverse(m1 / g, m2g);
    ll k = (ll)((__int128)(a2 - a1) / g % m2g * inv % m2g);
    k = (k + m2g) % m2g;
    ll M = m1 / g * m2; // lcm(m1, m2)
    ll ans = a1 + m1 * k;
    return {(ans % M + M) % M, M};
}

int main() {
    // Example: solve 3x = 1 (mod 7)
    cout << "3^{-1} mod 7 = " << mod_inverse(3, 7) << "\n"; // 5

    // Example: 6x + 10y = 8
    auto [x0, y0, g] = solve_diophantine(6, 10, 8);
    cout << "6*" << x0 << " + 10*" << y0 << " = 8\n";

    // Example: x=2(mod 3), x=3(mod 5)
    auto [r1, M1] = crt(2, 3, 3, 5);
    cout << "CRT: x = " << r1 << " (mod " << M1 << ")\n"; // 8 mod 15

    // Example: x=3(mod 6), x=5(mod 10)  (non-coprime)
    auto [r2, M2] = crt_general(3, 6, 5, 10);
    cout << "General CRT: x = " << r2 << " (mod " << M2 << ")\n"; // 15 mod 30

    return 0;
}

Explained Version (With Comments)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Extended Euclidean Algorithm
// Given a, b, finds x, y such that a*x + b*y = gcd(a, b).
// Returns gcd(a, b). x and y are set by reference.
//
// Base case: gcd(a, 0) = a, achieved by x=1, y=0 (a*1 + 0*0 = a).
// Recursive step: if we know b*x1 + (a%b)*y1 = g,
//   then a*y1 + b*(x1 - floor(a/b)*y1) = g.
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    // Back-substitute: from b*x1 + (a - (a/b)*b)*y1 = g
    // we get a*y1 + b*(x1 - (a/b)*y1) = g
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular Inverse
// Returns x such that a*x = 1 (mod m), or -1 if gcd(a,m) != 1.
// Works for any m (prime or composite), as long as gcd(a, m) = 1.
//
// Key idea: extgcd gives a*x + m*y = 1, so a*x = 1 (mod m).
// The result x might be negative, so we normalize to [0, m).
ll mod_inverse(ll a, ll m) {
    ll x, y;
    ll g = extgcd(a, m, x, y);
    if (g != 1) return -1;  // no inverse: a and m share a factor
    return (x % m + m) % m; // normalize negative results
}

// Solve the linear Diophantine equation: a*x + b*y = c
// Returns {x0, y0, gcd(a,b)} if solution exists, {0, 0, 0} otherwise.
//
// A solution exists iff gcd(a,b) divides c.
// If (x', y') satisfies a*x' + b*y' = g, then
// x0 = x' * (c/g), y0 = y' * (c/g) satisfies a*x0 + b*y0 = c.
//
// General solution: x = x0 + (b/g)*t, y = y0 - (a/g)*t for any integer t.
tuple<ll,ll,ll> solve_diophantine(ll a, ll b, ll c) {
    ll x, y;
    ll g = extgcd(abs(a), abs(b), x, y);
    if (c % g != 0) return {0, 0, 0}; // no solution
    x *= c / g;
    y *= c / g;
    // extgcd works on |a|, |b|; fix signs
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return {x, y, g};
}

// Chinese Remainder Theorem (coprime moduli)
// Solves: x = a1 (mod m1), x = a2 (mod m2), where gcd(m1, m2) = 1.
// Returns {r, m1*m2} such that x = r (mod m1*m2).
//
// Write x = a1 + m1*k. Substituting into second congruence:
// a1 + m1*k = a2 (mod m2)  =>  k = (a2 - a1) * m1^{-1} (mod m2).
// The inverse m1^{-1} mod m2 exists because gcd(m1, m2) = 1.
pair<ll,ll> crt(ll a1, ll m1, ll a2, ll m2) {
    ll inv = mod_inverse(m1, m2);
    // Compute k = (a2 - a1) * inv (mod m2), carefully handling negatives
    ll diff = ((a2 - a1) % m2 + m2) % m2;
    ll k = diff * inv % m2;
    ll M = m1 * m2;
    ll ans = a1 + m1 * k;
    return {(ans % M + M) % M, M};
}

// General CRT (moduli need NOT be coprime)
// Solves: x = a1 (mod m1), x = a2 (mod m2).
// Returns {r, lcm(m1,m2)} or {-1, -1} if no solution.
//
// Let g = gcd(m1, m2). A solution exists iff g | (a2 - a1).
// After dividing by g, we solve:
//   (m1/g) * k = (a2-a1)/g  (mod m2/g)
// The inverse of (m1/g) mod (m2/g) exists since gcd(m1/g, m2/g) = 1.
// Combined modulus is lcm(m1, m2) = m1 * m2 / g.
//
// Uses __int128 to prevent overflow in intermediate multiplication.
pair<ll,ll> crt_general(ll a1, ll m1, ll a2, ll m2) {
    ll g = gcd(m1, m2);
    if ((a2 - a1) % g != 0) return {-1, -1}; // inconsistent system
    ll m2g = m2 / g;
    ll inv = mod_inverse(m1 / g, m2g);
    // k = ((a2 - a1) / g) * inv (mod m2/g), using 128-bit to avoid overflow
    ll k = (ll)((__int128)(a2 - a1) / g % m2g * inv % m2g);
    k = (k + m2g) % m2g;
    ll M = m1 / g * m2; // lcm(m1, m2), computed to minimize overflow risk
    ll ans = a1 + m1 * k;
    return {(ans % M + M) % M, M};
}

int main() {
    // --- Modular inverse ---
    // 3^{-1} mod 7 should be 5 (since 3*5 = 15 = 1 mod 7)
    cout << "3^{-1} mod 7 = " << mod_inverse(3, 7) << "\n";

    // 5^{-1} mod 12 should be 5 (since 5*5 = 25 = 1 mod 12)
    cout << "5^{-1} mod 12 = " << mod_inverse(5, 12) << "\n";

    // --- Linear Diophantine ---
    // 6x + 10y = 8: gcd(6,10)=2 divides 8, so solvable
    auto [x0, y0, g] = solve_diophantine(6, 10, 8);
    cout << "6*" << x0 << " + 10*" << y0 << " = 8";
    cout << " (general: x=" << x0 << "+5t, y=" << y0 << "-3t)\n";

    // --- CRT (coprime) ---
    // x=2(mod 3), x=3(mod 5) => x=8(mod 15)
    auto [r1, M1] = crt(2, 3, 3, 5);
    cout << "CRT: x = " << r1 << " (mod " << M1 << ")\n";

    // --- General CRT (non-coprime) ---
    // x=3(mod 6), x=5(mod 10) => gcd(6,10)=2 divides (5-3)=2 => solvable
    auto [r2, M2] = crt_general(3, 6, 5, 10);
    cout << "General CRT: x = " << r2 << " (mod " << M2 << ")\n";

    return 0;
}

---

Operations Reference

Operation	Time Complexity	Space Complexity	Notes
extgcd(a, b)	$O(\log (min(a,b)))$	$O(\log (min(a,b)))$ recursion stack	Same as standard GCD
mod_inverse(a, m)	$O(\log m)$	$O(\log m)$	Requires $gcd(a,m)=1$
solve_diophantine(a, b, c)	$O(\log (min(a,b)))$	$O(\log (min(a,b)))$	One particular solution
crt(a1, m1, a2, m2)	$O(\log m_2)$	$O(\log m_2)$	Coprime moduli only
crt_general(a1, m1, a2, m2)	$O(\log m_2)$	$O(\log m_2)$	Works for any moduli
CRT for $k$ congruences	$O(k\log M)$	$O(1)$ extra if iterative	Apply pairwise; $M=max(m_i)$

---

Problem Patterns & Tricks

Pattern 1: Modular Inverse Under Non-Prime Moduli

When the problem gives a modulus that isn't guaranteed to be prime (or is a prime power, or composite), Fermat's little theorem won't work. Use extended GCD instead.

// Safe inverse that works for any m with gcd(a, m) = 1
ll safe_inv(ll a, ll m) { return mod_inverse(a, m); }

This comes up frequently in problems involving modular arithmetic where the modulus is an input parameter.

Problems: CF 1916E, CF 300C

Pattern 2: Systems of Congruences

You're given several conditions like "remainder $r_i$ when divided by $m_i$" and need to find the smallest positive number satisfying all of them (or count solutions in a range). Apply CRT iteratively:

ll r = a[0], M = m[0];
for (int i = 1; i < n; i++) {
    auto [nr, nM] = crt_general(r, M, a[i], m[i]);
    if (nM == -1) { /* no solution */ }
    r = nr; M = nM;
}
// x = r (mod M) is the combined solution

Problems: CSES 1712 (Exponentiation II), CF 687B

Pattern 3: Linear Diophantine with Bounds

Find the number of non-negative integer solutions to $ax+by=c$ where $L_x\le x\le R_x$ and $L_y\le y\le R_y$.

First find any solution $(x_0,y_0)$, then the general solution has parameter $t$. Constrain $t$ from both the $x$ and $y$ bounds and count integers in the intersection.

auto [x0, y0, g] = solve_diophantine(a, b, c);
if (g == 0) { /* no solution */ }
ll step_x = b / g, step_y = a / g;
// x = x0 + step_x * t >= Lx  =>  t >= ceil((Lx - x0) / step_x)
// similar for upper bounds and y constraints
// count valid t values

Problems: CF 1244C, CF 710D

Pattern 4: Reconstructing Values from Multiple Mods

When intermediate results would overflow, compute them modulo several coprime moduli and reconstruct the answer using CRT. This is the basis of NTT-based polynomial multiplication using multiple NTT-friendly primes.

Common NTT primes: $998244353$, $985661441$, $754974721$ -- all have large power-of-2 factors in $(p-1)$ and are pairwise coprime.

Problems: CF 1036G

Pattern 5: Modular Equation Solving

Solve $ax\equiv b(\mathrm{mod}m)$. Let $g=gcd(a,m)$. If $g\nmid b$, no solution. Otherwise, divide everything by $g$: solve $\frac{a}{g}x\equiv \frac{b}{g}(\mathrm{mod}\frac{m}{g})$. Now $gcd(\frac{a}{g},\frac{m}{g})=1$, so multiply by the inverse.

There are exactly $g$ solutions modulo $m$ (one base solution plus offsets of $m/g$).

// all solutions to ax = b (mod m) in [0, m)
vector<ll> solve_linear_mod(ll a, ll b, ll m) {
    ll g = gcd(a, m);
    if (b % g != 0) return {};
    a /= g; b /= g; ll mg = m / g;
    ll x0 = (ll)(((__int128)b * mod_inverse(a, mg)) % mg);
    x0 = (x0 + mg) % mg;
    vector<ll> res;
    for (ll i = 0; i < g; i++)
        res.push_back(x0 + i * mg);
    return res;
}

Problems: CF 1748D

Pattern 6: Chicken McNugget / Frobenius

For $gcd(a,b)=1$, the largest number that cannot be represented as $ax+by$ with $x,y\ge 0$ is $ab-a-b$. To check if a specific $c$ is representable, solve the Diophantine equation and check if any solution has both $x\ge 0$ and $y\ge 0$.

Problems: CF 1183F

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|  EXTENDED GCD / CRT  --  Quick Reference                     |
+--------------------------------------------------------------+
|                                                               |
|  extgcd(a, b, x, y) -> g, with a*x + b*y = g                |
|  mod_inverse(a, m)   -> a^{-1} mod m  (needs gcd(a,m)=1)    |
|                                                               |
|  WHEN TO USE:                                                 |
|  * Modular inverse, mod not guaranteed prime -> extgcd        |
|  * a*x + b*y = c  integer solutions         -> diophantine   |
|  * System of x=ai(mod mi)                   -> CRT pairwise  |
|  * Moduli not coprime                        -> general CRT   |
|                                                               |
|  KEY FORMULAS:                                                |
|  * a*x + b*y = c solvable  <=>  gcd(a,b) | c                 |
|  * General soln: x = x0 + (b/g)*t,  y = y0 - (a/g)*t        |
|  * CRT combined mod = lcm(m1, m2)                             |
|                                                               |
|  COMPLEXITY:  O(log min(a,b)) per call                        |
|                                                               |
|  WATCH OUT:                                                   |
|  * Normalize negative x:  x = (x % m + m) % m                |
|  * Overflow in CRT:  use __int128 for intermediate products   |
|  * gcd(a,m) != 1  =>  no inverse exists                       |
+--------------------------------------------------------------+

---

Gotchas & Debugging

Negative results from extgcd. The $x$ and $y$ returned can be negative. If you need a modular inverse, always normalize: (x % m + m) % m. Forgetting this is the single most common bug.

Overflow in CRT. When combining $x=a_1+m_1\cdot k$, the product $m_1\cdot k$ can overflow long long if $m_1$ and $k$ are both up to ${10}^9$. Use __int128 for the intermediate multiplication, or restructure the computation. The combined modulus $m_1\cdot m_2$ itself might also overflow -- check whether the problem guarantees it fits in 64 bits.

Forgetting the divisibility check. For $ax+by=c$, if you skip checking $gcd(a,b)\mid c$, you'll get garbage. For general CRT, if $gcd(m_1,m_2)$ doesn't divide $a_2-a_1$, there's no solution -- don't return a wrong answer.

Negative inputs to extgcd. The standard recursive implementation assumes $a,b\ge 0$. If your $a$ or $b$ can be negative (common in Diophantine problems), call extgcd(|a|, |b|, x, y) and flip the sign of $x$ or $y$ afterwards.

Off-by-one in solution counting. When counting solutions of $ax+by=c$ in a range, be careful with the ceiling/floor divisions for the parameter $t$. Integer division in C++ truncates toward zero, not toward negative infinity. Use:

// floor division that works for negative dividends
ll floor_div(ll a, ll b) {
    return a / b - (a % b != 0 && (a ^ b) < 0);
}
ll ceil_div(ll a, ll b) {
    return a / b + (a % b != 0 && (a ^ b) > 0);
}

Iterative CRT accumulation. When combining $k$ congruences pairwise, the modulus grows. If you're not careful, the intermediate modulus can overflow before you finish. Always use __int128 or restructure so that no intermediate value exceeds 64 bits.

Zero modulus edge case. If any $m_i=0$ or any $a_i$ is out of range, handle it before calling CRT. Garbage in, garbage out.

Mental Traps

"I can just use pow(a, MOD-2, MOD) for modular inverse." This works for prime MOD (by Fermat's little theorem). But for composite moduli, or when $gcd(a,m)>1$ (inverse doesn't exist), Fermat's approach gives wrong results silently. Extended Euclid is the general tool; Fermat's is a special case. Always ask: "Is my modulus guaranteed prime?"

"CRT = combine two congruences into one." True but incomplete. CRT also tells you the combined congruence has a unique solution modulo $\text{lcm}(m_1,m_2)$. Forgetting the "modulo lcm" part means you output a specific solution without knowing its period -- wrong for problems that want the smallest non-negative solution or that ask about the general solution.

"Extended Euclid only works for $gcd(a,b)=1$." Extended Euclid works for any $a,b$ and gives $ax+by=gcd(a,b)$. Modular inverse specifically requires $gcd(a,m)=1$. The algorithm is strictly more general than the inverse application. Don't restrict your thinking to just the inverse use case.

MENTAL TRAP MAP:
+-----------------------------------------------------------+
|                                                           |
|  "Use Fermat"  --->  WRONG if mod is composite            |
|       |              or gcd(a, m) > 1                     |
|       v                                                   |
|  Extended Euclid  --->  GENERAL: works for any a, b       |
|       |                                                   |
|       +---> gives ax + by = gcd(a,b)                      |
|       |         |                                         |
|       |         +---> if gcd = 1: x is modular inverse    |
|       |         +---> if gcd > 1: no inverse, but         |
|       |                  Diophantine solutions exist       |
|       |                                                   |
|  "CRT = one answer" ---> INCOMPLETE                       |
|       |                                                   |
|       +---> Answer is x (mod lcm(m1, m2))                 |
|             The PERIOD matters for follow-up queries       |
+-----------------------------------------------------------+

"The parametric family is just for theory -- I only need one solution." The parametric form $x=x_0+(b/g)\cdot t$ is essential whenever a problem asks "how many solutions in range $[L,R]$?" You need to solve $L\le x_0+(b/g)\cdot t\le R$ for integer $t$, which gives $t_{min}=\lceil (L-x_0)/(b/g)\rceil$ and $t_{max}=\lfloor (R-x_0)/(b/g)\rfloor$. Answer: $t_{max}-t_{min}+1$ (if $\ge 0$). Without the parametric form, you're stuck.

"I'll compute all pairwise CRTs in any order -- it's associative." CRT merging is associative for correctness, but not for overflow safety. If you merge two large moduli first (say ${10}^9$ and ${10}^9$), the combined modulus is $\sim {10}^{18}$ and the next merge does arithmetic near ${10}^{27}$ -- instant overflow even with __int128. Always merge smallest moduli first, or better yet, use Garner's algorithm to avoid the issue entirely.

OVERFLOW TRAP -- merge order matters:

  Moduli: m1=10⁹, m2=10⁹, m3=17

  BAD ORDER (merge large first):
  ┌──────┐  ┌──────┐
  │ 10⁹  │  │ 10⁹  │
  └──┬───┘  └──┬───┘
     └────┬────┘
          v
   combined: mod 10¹⁸  <- already near int64 limit!
          │    ┌────┐
          └──┬─┤ 17 │
             v └────┘
      mod 17*10¹⁸      <- OVERFLOW: needs ~10¹⁹

  GOOD ORDER (merge small first):
  ┌────┐  ┌──────┐
  │ 17 │  │ 10⁹  │
  └─┬──┘  └──┬───┘
    └────┬────┘
         v
   combined: mod 17*10⁹  <- fits in int64 easily
         │    ┌──────┐
         └──┬─┤ 10⁹  │
            v └──────┘
     mod 17*10¹⁸         <- same result, but intermediates
                             stayed smaller throughout!

  BEST: use Garner's algorithm -- each step works mod mᵢ only.

Trap: "I only need extended GCD for modular inverse -- I can skip linear Diophantine equations."

Linear Diophantine equations ($ax+by=c$) appear more often than you'd expect: scheduling problems ("every $a$ days and every $b$ days, when do events coincide?"), counting lattice points in regions, and coin-change-style problems where you need all solutions, not just one. Extended GCD gives you the particular solution; the parametric family gives you the rest. Skipping Diophantine equations means you can't solve half the problems that use this machinery.

DIOPHANTINE EQUATION -- when you need ALL solutions:

  Problem: "Find all (x,y) with 15x + 21y = 12, 0 <= x <= 100"

  Step 1: gcd(15,21) = 3,  3 | 12  -> solutions exist
  Step 2: ExtGCD gives 15*(-4) + 21*(3) = 3
          Scale by 12/3 = 4: x₀ = -16, y₀ = 12
  Step 3: General solution:
          x = -16 + 7t      (step = 21/3 = 7)
          y =  12 - 5t      (step = -15/3 = -5)
  Step 4: 0 <= -16 + 7t <= 100
          16/7 <= t <= 116/7
          ⌈2.28⌉ <= t <= ⌊16.57⌋
          3 <= t <= 16  ->  14 solutions

  ┌────────────────────────────────────────┐
  │ Without the parametric form, you       │
  │ can't count solutions in a range.      │
  │ This is the WHOLE POINT of learning    │
  │ Diophantine equations properly.        │
  └────────────────────────────────────────┘

Trap: "Negative Bézout coefficients are a cosmetic issue -- just add $m$ at the end."

It's not cosmetic; it's the #1 source of bugs. The formula (x % m + m) % m works, but ONLY if you apply it immediately after extgcd returns. If you use the raw negative x in further arithmetic (multiplying by $c/g$, combining CRT steps), intermediate results can underflow or behave unexpectedly with C++ integer division (which truncates toward zero, not toward $-\mathrm{\infty }$). Normalize early, not late.

NEGATIVE COEFFICIENT BUG TIMELINE:

  extgcd(7, 15, x, y) returns x = -2, y = 1
  (7*(-2) + 15*1 = 1  OK)

  X BAD: use x = -2 directly in CRT merge
    k = (a2 - a1) * x % m2    <- C++ computes (-2) % 15 = -2
    a1 + m1 * k               <- m1 * (-2) gives negative result
    The final answer might be negative -> WA

  OK GOOD: normalize immediately
    x = (x % m + m) % m = (-2 % 15 + 15) % 15 = 13
    k = (a2 - a1) * 13 % m2   <- always non-negative
    a1 + m1 * k                <- always positive

---

Common Mistakes

1. Not normalizing x. Extended GCD can return negative x. Fix: x = ((x % (b/g)) + (b/g)) % (b/g) to get the smallest non-negative solution.
2. Forgetting to scale for Diophantine equations. Extended GCD solves ax + by = g. For ax + by = c, multiply x and y by c / g.
3. CRT with non-coprime moduli. When gcd(m1, m2) > 1, check gcd(m1, m2) | (r1 - r2) first. If it fails, no solution exists.
4. Overflow in CRT combination. The combined modulus m1 * m2 can overflow long long. Use __int128 or restructure the computation.
5. Confusing extended GCD with standard GCD. Extended GCD returns (g, x, y). If you only check g and ignore x, y, you've just computed regular GCD with extra overhead.
6. Assuming CRT moduli are coprime. Standard CRT merges m_1, m_2 into a combined modulus m_1 \cdot m_2 -- but when \gcd(m_1, m_2) > 1, that product is wrong because $\mathrm{lcm}(m_1,m_2)\ne m_1\cdot m_2$. Merging two congruences whose moduli share a common factor of 3 without noticing will pass samples and then WA on a deeper test. The fix is general CRT: merge using $\mathrm{lcm}(m_1,m_2)=m_1\cdot m_2/gcd(m_1,m_2)$, and check compatibility (gcd(m_1, m_2) | (r_2 - r_1)) before every merge. Always ask: "Are these moduli coprime?" If the problem doesn't guarantee it, use general CRT.

Debug Drills

Drill 1. extgcd returns wrong inverse.

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long mod_inverse(long long a, long long m) {
    long long x, y;
    extgcd(a, m, x, y);
    return x % m;  // What's wrong?
}

What's wrong?

x can be negative after extgcd. x % m in C++ preserves the sign, so you get a negative "inverse." Fix: return (x % m + m) % m;

Drill 2. CRT overflow.

long long crt(long long r1, long long m1, long long r2, long long m2) {
    long long g = __gcd(m1, m2);
    if ((r2 - r1) % g != 0) return -1;  // no solution
    long long lcm = m1 / g * m2;
    long long x, y;
    extgcd(m1 / g, m2 / g, x, y);
    long long diff = (r2 - r1) / g;
    long long t = diff * x % (m2 / g);  // What's wrong?
    return r1 + m1 * t;  // potential issue?
}

What's wrong?

Two issues: (1) diff * x can overflow if both are large -- use (__int128)diff * x % (m2/g). (2) t might be negative (same C++ modulus sign issue), so add (t % (m2/g) + m2/g) % (m2/g). (3) r1 + m1 * t can also overflow -- normalize the final result mod lcm.

Drill 3. Diophantine equation forgets to scale.

// Solve a*x + b*y = c
bool solve(long long a, long long b, long long c, long long &x, long long &y) {
    long long g = extgcd(a, b, x, y);
    if (c % g != 0) return false;
    // x, y now satisfy a*x + b*y = g
    // But we need a*x + b*y = c!
    return true;  // What's missing?
}

What's wrong?

After finding x, y for a*x + b*y = g, you must scale: x *= c / g; y *= c / g; to get a solution for a*x + b*y = c. Without scaling, you've solved the wrong equation.

---

Self-Test

Before moving on, verify you can handle these without looking at the notes:

1. Write the extended Euclidean algorithm from memory -- it should return $(g,x,y)$ such that $ax+by=g$. Test it on $a=161,b=28$.

2. Compute $7^{-1}mod15$ by hand -- use extended Euclid, normalize the result, and verify $7\cdot x\equiv 1(\mathrm{mod}15)$.

3. Solve two congruences by CRT -- $x\equiv 3(\mathrm{mod}5)$, $x\equiv 2(\mathrm{mod}7)$. Find the unique solution modulo 35 and verify both congruences.

4. State when a system of two congruences has no solution -- give a concrete example where $gcd(m_1,m_2)>1$ and no $x$ exists.

5. Explain why Fermat's little theorem fails for composite moduli -- and what extended GCD offers instead.

6. Find all solutions to $6x+10y=8$ with $0\le x\le 20$ -- write out the parametric family and count valid $t$ values.

7. Combine three congruences using pairwise CRT -- $x\equiv 1(\mathrm{mod}2)$, $x\equiv 2(\mathrm{mod}3)$, $x\equiv 3(\mathrm{mod}5)$. Show each merge step.

• [ ] Count solutions to a linear Diophantine equation in a range -- Given $15x+21y=12$, find all solutions with $0\le x\le 100$. Write the parametric family, compute $t_{min}$ and $t_{max}$, and state the count.

• [ ] Implement Garner's algorithm from scratch -- Given congruences $x\equiv 2(\mathrm{mod}3)$, $x\equiv 3(\mathrm{mod}5)$, $x\equiv 2(\mathrm{mod}7)$, compute the mixed-radix coefficients $(r_1,r_2,r_3)$ by hand, then reconstruct $x$. Verify against pairwise CRT.

• [ ] Detect an unsolvable CRT system -- Given $x\equiv 3(\mathrm{mod}6)$ and $x\equiv 5(\mathrm{mod}10)$, show that $gcd(6,10)=2$ does not divide $5-3=2$... wait, it does. Find a pair where it genuinely fails (e.g., $x\equiv 3(\mathrm{mod}6)$ and $x\equiv 2(\mathrm{mod}4)$) and prove no solution exists.

• [ ] Compute a modular inverse under a composite modulus -- Find ${11}^{-1}(\mathrm{mod}24)$ using extended Euclid. Verify that Fermat's method (${11}^{22}mod24$) gives a wrong answer and explain why.

• [ ] Solve a CRT problem with non-coprime moduli -- $x\equiv 5(\mathrm{mod}12)$ and $x\equiv 11(\mathrm{mod}18)$. Check the solvability condition ($gcd(12,18)=6$ must divide $11-5=6$ -- it does). Find $x(\mathrm{mod}\text{lcm}(12,18))$ and verify.

• [ ] Trace extgcd(48, 18, x, y) by hand through all recursive calls, writing the $(x,y)$ values at each return level. Verify $48x+18y=6$.

• [ ] Given $x\equiv 5(\mathrm{mod}12)$ and $x\equiv 11(\mathrm{mod}18)$, check the solvability condition ($gcd(12,18)=6$, does $6\mid (11-5)$?), then solve using the general CRT formula. State $x(\mathrm{mod}\text{lcm}(12,18))$.

• [ ] Implement Garner's algorithm from scratch for three moduli -- compute mixed-radix coefficients by hand for $x\equiv 2(\mathrm{mod}3)$, $x\equiv 3(\mathrm{mod}5)$, $x\equiv 2(\mathrm{mod}7)$ and verify $x=23$.

• [ ] Find all non-negative solutions to $6x+10y=80$ -- write the parametric family, compute the valid $t$ range, and count the solutions.

• [ ] Explain why CRT merge order matters for overflow safety but not for correctness -- give a concrete example where merging two ${10}^9$-moduli first causes overflow in 64-bit arithmetic.

---

Practice Problems

Rating	You should be able to...
CF 1200	Know that modular inverse exists when gcd(a, m) = 1
CF 1500	Implement extended Euclidean; solve a*x ≡ b (mod m)
CF 1800	Apply CRT to combine congruences; handle non-coprime moduli with general CRT
CF 2100	Use CRT in DP optimizations; solve systems of linear Diophantine equations with bound constraints

#	Problem	Source	Difficulty	Key Technique
1	Exponentiation II	CSES	Easy	Modular inverse (Fermat or extgcd)
2	Modular Equations	CF 495B	Easy	Counting solutions to $amodx=b$
3	Beautiful Numbers	CF 300C	Medium	Combinatorics with modular inverse
4	NP-Hard Problem	CF 687B	Medium	Congruence systems / bipartite check
5	The Number of Solutions	CF 710D	Medium	Linear Diophantine with bounds
6	The Three Little Pigs	CF 1548C	Medium-Hard	CRT + roots of unity filter
7	Necklace	CF 613A	Medium	GCD / Diophantine on a cycle
8	Remainders Game	CF 687C	Hard	CRT uniqueness / prime power analysis
9	General CRT	Library Checker	Medium	Direct CRT implementation
10	Garland	CF 1279E	Hard	CRT in DP transitions

---

Further Reading

• Extended Euclidean Algorithm -- cp-algorithms.com
• Chinese Remainder Theorem -- cp-algorithms.com
• Linear Diophantine Equations -- cp-algorithms.com
• Modular Inverse -- cp-algorithms.com
• CRT Tutorial -- Codeforces Blog by adamant

---

Recap

• Extended GCD finds x, y such that ax + by = gcd(a,b). Use it for modular inverse when the modulus is not prime.
• Bezout's identity: ax + by = c has integer solutions if and only if gcd(a,b) divides c.
• CRT: given x = r_i (mod m_i) with pairwise coprime moduli, a unique solution exists mod m1 * m2 * ... * mk.
• Generalized CRT handles non-coprime moduli by checking compatibility via GCD.

---

Cross-Links

• Math Fundamentals -- modular arithmetic basics (Fermat inverse for prime mod)
• Number Theory -- primes, factorization, and Euler's totient
• Combinatorics Basics -- CRT appears in problems combining modular counting results