Linear congruence calculator
This online calculator solves linear congruences
This page exists due to the efforts of the following people:
 | Timur
|
This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/9561/. Also, please do not modify any references to the original work (if any) contained in this content.
Linear congruence solver
No solutions
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