Linear congruence calculator

This online calculator solves linear congruences

This page exists due to the efforts of the following people:

Timur

Timur

Created: 2021-11-26 23:13:53, Last updated: 2021-11-26 23:13:53

PLANETCALC, Linear congruence solver

Linear congruence solver

Linear congruence
 

No solutions

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

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 \equiv b {\pmod {m}}

A congruence of the form
 a \cdot x \equiv b {\pmod {m}}
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:
 a \cdot x + m \cdot y = b {\pmod {m}}

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.

URL copied to clipboard
PLANETCALC, Linear congruence calculator

Comments