# Linear congruence calculator

This online calculator solves linear congruences

### Esta página existe graças aos esforços das seguintes pessoas:

#### Timur

Criado: 2021-11-26 23:13:53, Ultima atualização: 2021-11-26 23:13:53

Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.

#### 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 copiado para a área de transferência