Linear congruence calculator
This online calculator solves linear congruences
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.
Comments