Skip to content
FiftyCalc Free calculators for all 50 states

Linear Congruence Calculator

Test cases replayed : 4 of 4 match · Methodology · No outside source listed

Enter whole numbers a, b and a modulus m. The calculator tells you whether ax ≡ b (mod m) has a solution and gives every solution as one residue class.

Result

Sample figures

Solution—

Smallest non-negative solution x₀ —

  • Solutions repeat every (m ÷ d)—
  • Number of solutions modulo m—
  • d = gcd(a, m)—

Estimate for planning only, not tax, legal, financial or medical advice. This calculator uses the method explained on this page.

Linear Congruence Calculator

Coefficient a (whole number): enter a number. Prefilled example: 14.

Right-hand side b (whole number): enter a number. Prefilled example: 30.

Modulus m (2 to 1,000,000): enter a number from 2 to 1,000,000. Prefilled example: 100.

How to use this calculator

Fill in the fields in this order; each step takes you to its field.

  1. Coefficient a (whole number): enter a number.
  2. Right-hand side b (whole number): enter a number.
  3. Modulus m (2 to 1,000,000): enter a number from 2 to 1,000,000.
  4. Read the result: Solution; the panel also shows Smallest non-negative solution x₀, Solutions repeat every (m ÷ d), Number of solutions modulo m and d = gcd(a, m).

How this calculator works

Linear congruence theorem: ax ≡ b (mod m) has a solution if and only if d = gcd(a, m) divides b. When it does, there are exactly d solutions modulo m.

Divide through by d: (a/d)x ≡ b/d (mod m/d). Now a/d and m/d share no factor, so a/d has an inverse modulo m/d, found with the extended Euclidean algorithm. Then x₀ = (b/d) × inverse, reduced modulo m/d.

Every solution is x = x₀ + k × (m/d) for any whole number k; the d values x₀, x₀ + m/d, …, x₀ + (d − 1)m/d are the distinct solutions modulo m.

Negative a or b are first reduced to their remainder between 0 and m − 1. Decimal entries are rounded to the nearest whole number.

Worked example

Coefficient a (whole number)14
Right-hand side b (whole number)30
Modulus m (2 to 1,000,000)100
Solutionx ≡ 45 (mod 50)
Smallest non-negative solution x₀45
Solutions repeat every (m ÷ d)50
Number of solutions modulo m2
d = gcd(a, m)2

Frequently asked questions

Why does 6x ≡ 4 (mod 9) have no solution?

gcd(6, 9) = 3, and 3 does not divide 4. Every value of 6x modulo 9 is 0, 3 or 6, so it can never equal 4.

How is this related to a modular inverse?

When gcd(a, m) = 1 and b = 1, the solution x₀ is the inverse of a modulo m: a × x₀ leaves remainder 1 when divided by m.

How do I check an answer?

Multiply a by x₀, subtract b and divide by m. The division must come out even. For 14x ≡ 30 (mod 100): 14 × 45 − 30 = 600, which is 6 × 100.

Related calculators