Linear congruence calculator

Linear congruence solver

Variable's coefficient

Right side of linear congruence

Modulus

Calculate

Linear congruence

 

No solutions

The file is very large. Browser slowdown may occur during loading and creation.

Download 

 Link  Save  Widget

Linear Congruence

Given an integer m > 1, called a modulus, two integers a and b are said to be congruent modulo m if m is a divisor of their difference. The system of arithmetic for integers, where numbers "wrap around" the modulus, is called the modular arithmetic.

Congruence modulo m is denoted like this:

A congruence of the form

is called a linear congruence in one variable.

To check for the existence of congruence solutions, you should find the GCD(a, m). If b is not a multiple of the resulting GCD, then the congruence has no solutions.
If it is a multiple, then the number of solutions modulo m is equal to the resulting GCD.

There are several algorithms for finding all linear congruence solutions, this calculator uses an algorithm for solving linear Diophantine equations in two variables. Indeed, the linear congruence is an equivalent to the following linear Diophantine equation:

I used the already implemented calculator for linear Diophantine equations to obtain the general solution formula, then I selected all solutions in the range from 0 to m.