✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-076

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

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.

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