Linear Congruences
Solve ax ≡ b (mod n).
Key idea
Solve ax ≡ b (mod n).
In depth
ax ≡ b (mod n) has a solution iff gcd(a, n) | b. If g = gcd(a, n) divides b, there are g solutions mod n. Divide through by g, then multiply by the inverse.
Worked example
3x ≡ 4 (mod 7): inverse of 3 is 5, so x ≡ 20 ≡ 6.
Real-world uses
- Solving scheduling problems that repeat every few days or weeks
Common mistake
Dividing by a without checking invertibility.
How to learn this
- Read the key idea and say it in your own words.
- Work through the worked example, then try a similar problem.
- Use the interactive lesson’s visual and mini-quiz to check the pattern.
Frequently asked questions
What is Linear Congruences?
Solve ax ≡ b (mod n). It is a topic at the expert level in Discrete Math & Number Theory.
Where is Linear Congruences used in real life?
Real-world examples: Solving scheduling problems that repeat every few days or weeks.
What should I learn before Linear Congruences?
Make sure you are comfortable with Modular Inverses, the previous topic in Discrete Math & Number Theory.
What is a common mistake with Linear Congruences?
Dividing by a without checking invertibility.
How can I practise Linear Congruences?
Open the interactive lesson, play with the visual, then answer the three-question mini-quiz. Getting two right marks the topic complete.
What comes after Linear Congruences?
Move on to Chinese Remainder Theorem next.
Related expert topics in Discrete Math & Number Theory
- Strong Induction – Assume all earlier cases to prove the next.
- Well-Ordering Principle – Every nonempty set of positive integers has a least element.
- Partial Orders – Reflexive, antisymmetric, transitive relations.
- Cardinality of Sets – Comparing sizes of infinite sets.
- Countable and Uncountable Sets – ℕ and ℚ are countable; ℝ is not.
- Cantor’s Diagonal Argument – Proof that real numbers are uncountable.