--- 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-09-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. **Example.** The Chinese remainder theorem combines congruences with coprime moduli into one. Mod 4 and mod 9 merge into mod 36, and mod 5 with mod 7 merges into mod 35. The smallest x that is 1 mod 4 and 2 mod 5 is 17: candidates 1, 5, 9, 13 reduce mod 5 to 1, 0, 4, 3, and 17 is the first to give 2. The proof builds its solution out of one inverse per modulus. **Tip.** Work each congruence in this order. First check the gcd rule for solvability and count the solutions. Then invert with Euclid run backwards to isolate x. Only combine moduli that are coprime, and state the answer modulo their product. **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)