A linear congruence has the general form ax ≡ b (mod n), where a, b, and n are integers and n is positive. To determine whether a solution exists, calculate d = gcd(a, n). A solution exists if and only if d divides b. If this condition holds, there are exactly d incongruent solutions modulo n. When gcd(a, n) = 1, there is exactly one solution modulo n, and it can be found by multiplying both sides by the modular inverse of a. When d is greater than 1, the equation can be reduced by dividing a, b, and n by d, after which the reduced coefficient has an inverse modulo the reduced modulus. Linear congruences are important in elementary number theory, cryptography, and problems involving integer remainders.
Linear Congruences
A linear congruence is a modular equation of the form ax ≡ b (mod n). Its solvability and number of solutions depend on the greatest common divisor of a and n.
ax ≡ b (mod n) has a solution ⇔ gcd(a, n) | b
Explanation
Variables
A
The coefficient of the unknown x.
X
The unknown integer.
B
The constant term.
N
The positive modulus.
D
The greatest common divisor gcd(a, n).
Example or application
Problem
Solve 3x ≡ 4 (mod 7).
Solution
The inverse of 3 modulo 7 is 5 because 3 × 5 ≡ 1 (mod 7). Multiply both sides by 5: x ≡ 5 × 4 ≡ 20 ≡ 6 (mod 7).
Answer
x ≡ 6 (mod 7)
Text
The solvability condition for a linear congruence is determined by the greatest common divisor of its coefficient and modulus. The modular inverse method provides a direct solution when the coefficient and modulus are relatively prime.
Key Points
The general form is ax ≡ b (mod n).
A solution exists if and only if gcd(a, n) divides b.
If gcd(a, n) = 1, there is exactly one solution modulo n.
If d = gcd(a, n) divides b, there are exactly d incongruent solutions modulo n.
Modular inverses can solve congruences when the coefficient is relatively prime to the modulus.
A congruence with a non-coprime coefficient may have no solution or multiple solutions.
Applications
Solving remainder-based integer problems.
Finding unknown values in modular systems.
Cryptographic calculations.
Analyzing periodic and cyclic processes.
Solving systems of congruences.
Learning Outcomes
Recognize and define a linear congruence.
Test whether a linear congruence has a solution.
Solve linear congruences using modular inverses.
Determine the number of incongruent solutions.
Practice Questions
Solve 5x ≡ 3 (mod 8).
Determine whether 6x ≡ 5 (mod 9) has a solution.
Solve 4x ≡ 8 (mod 12).
How many incongruent solutions does 6x ≡ 12 (mod 18) have?
State the necessary and sufficient condition for ax ≡ b (mod n) to be solvable.
Related Concepts
Modular Inverses
Greatest Common Divisor
Extended Euclidean Algorithm
Chinese Remainder Theorem
Congruence Relations
Common Mistakes
Assuming every linear congruence has a solution.
Using a modular inverse when the coefficient is not relatively prime to the modulus.
Ignoring the condition gcd(a, n) | b.
Failing to list all incongruent solutions when the greatest common divisor is greater than 1.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Kenneth H. Rosen, Elementary Number Theory and Its Applications
- David M. Burton, Elementary Number Theory
Suggest a correction or source · More in Arithmetic & Number Theory