--- title: "Linear Congruences and the Chinese Remainder Theorem" description: "Solve a single linear congruence, say exactly when it is solvable, and combine congruences with coprime moduli into one." canonical: https://lightmysky.com/learn/mathematics/linear-congruences-and-the-chinese-remainder-theorem-mt_J9_RMpwcRX source: https://lightmysky.com/learn/mathematics/linear-congruences-and-the-chinese-remainder-theorem-mt_J9_RMpwcRX.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Linear Congruences and the Chinese Remainder Theorem Solve a single linear congruence, say exactly when it is solvable, and combine congruences with coprime moduli into one. Subject: Mathematics · Area: Number Theory · Ages 19 to 20 Page: https://lightmysky.com/learn/mathematics/linear-congruences-and-the-chinese-remainder-theorem-mt_J9_RMpwcRX ## Ready when they can - Decide when a linear congruence has a solution and count the solutions modulo n - Find a modular inverse using the extended Euclidean algorithm - Solve a system of congruences with coprime moduli and state the modulus of the combined answer ## Lesson: Solving congruences and combining remainders A linear congruence a x is b mod n asks which remainder family x must come from. It has a solution exactly when the gcd of a and n divides b. So 2x is 3 mod 6 is impossible, since gcd 2 skips 3. When the gcd does divide b, there are exactly that many solutions mod n: 6x is 9 mod 15 has 3, since gcd(6, 15) is 3 and 3 divides 9. An inverse of a mod n is a number u with a times u is 1 mod n, and it exists exactly when a and n are coprime. The inverse of 3 mod 7 is 5, since 15 leaves remainder 1. The inverse of 4 mod 9 is 7, since 28 leaves remainder 1. Euclid finds the gcd fast by repeated division, and running it backwards writes the gcd as a combination of a and n, which is exactly how you compute an inverse by hand. *(drawing: Coprime moduli multiply: 4 and 9 give 36. Listing 1 mod 4 gives 1, 5, 9, 13, 17, and 17 is first with 2 mod 5.)* **Tip.** Work each congruence in this order. First check the gcd rule for solvability and count the solutions. When a and n are coprime, invert with Euclid run backwards to isolate x. Only combine moduli that are coprime, and state the answer modulo their product. Check inverses by multiplying out. 4 times 7 is 28, and 28 is 3 times 9 plus 1, so 7 inverts 4 mod 9. Trying 2 gives 8 and trying 5 gives 20, neither leaving 1. Run Euclid backwards to invert by hand. First divide repeatedly to get the gcd, then rewrite each remainder from the line above. When the gcd is 1 the coefficient of a is its inverse. **Recap.** Check the gcd for solvability, invert with Euclid run backwards, and multiply coprime moduli into one. ## Practice 16 questions on this page, each with its working shown. ## Needs first - [Modular Arithmetic and Congruence Classes](https://lightmysky.com/learn/mathematics/modular-arithmetic-and-congruence-classes-mt_Lt4_Aazx2j) ## Opens up - [Fermat's Little Theorem and Euler's Theorem](https://lightmysky.com/learn/mathematics/fermats-little-theorem-and-eulers-theorem-mt_7wW4z4Eidx)