Course contentsShow
← Mathematics
Lesson 2752 of 3,12154. Number TheoryFree lesson

Systems of Linear Congruences

Understand what it means to solve multiple congruences simultaneously and why they arise in number theory.

Systems of Linear Congruences

What you'll learn: You'll discover why we sometimes need to solve multiple modular equations at once and what that really means.

The Core Problem

Imagine you're told a number leaves remainder 2 when divided by 5, and remainder 3 when divided by 7. What could that number be? This is a system of linear congruences:

x ≡ 2 (mod 5)
x ≡ 3 (mod 7)

Just as you might solve a system of regular equations (like x + y = 5 and 2x - y = 1) to find values satisfying both conditions, here you're hunting for integers that satisfy multiple modular conditions simultaneously.

Why They Matter

Systems of congruences arise naturally in number theory:

  • Calendar problems: "What day will it be 100 days from now?" involves cycles of different lengths
  • Cryptography: Many encryption methods require finding numbers with specific remainders under different moduli
  • Scheduling: Coordinating events with different repeating patterns
  • Ancient problems: The Chinese Remainder Theorem (which you'll learn next) was developed to solve counting problems involving different-sized groups

What "Solving" Means

A solution is an integer (or set of integers) satisfying all congruences in the system. Sometimes there's no solution, sometimes one unique solution modulo a certain number, and sometimes infinitely many solutions.

For example, x ≡ 2 (mod 5) alone has solutions x = 2, 7, 12, 17, 22, ... Adding the second condition narrows this down dramatically—perhaps to just one possibility in a certain range.

Key Takeaway: A system of linear congruences asks you to find numbers that simultaneously satisfy multiple modular remainder conditions, a problem that appears throughout number theory and its applications.