x ≡ (mod )

## FAQs & How-to's

#### What is this calculator for?

This is a linear congruence solver made for solving equations of the form $$ax \equiv b \; ( \text{mod} \; m)$$, where $$a$$, $$b$$ and $$m$$ are integers, and $$m$$ is positive.

#### Can I embed this on my website?

Sure. Embedding is allowed as long as you promise to follow our conditions. Here's the embed code:

 <iframe width="415" height="220" src="http://www.a-calculator.com/congruence/embed.html" frameborder="0" allowtransparency="true"></iframe> 

#### How do I solve a linear congruence equation manually?

The calculations are somewhat involved. In an equation $$ax \equiv b \; ( \text{mod} \; m)$$ the first step is to reduce $$a$$ and $$b$$ mod $$m$$. For example, if we start off with $$a = 28$$, $$b = 14$$ and $$m = 6$$ the reduced equation would have $$a = 4$$ and $$b = 2$$.

Next we use the extended Euclidean algorithm to find two numbers, $$p$$ and $$q$$ such that \begin{equation*} ap + mq = \text{gcd}(a, m). \end{equation*} (Even though the algorithm finds both $$p$$ and $$q$$, we only need $$p$$ for this.)

Now, unless $$\text{gcd}(a, m)$$ evenly divides $$b$$ there won't be any solutions to the linear congruence. Though if it does, our first solution is given by \begin{equation*} x_0 = \frac{bp}{\text{gcd}(a, m)} \; ( \text{mod} \; m). \end{equation*} The remaining solutions are given by \begin{equation*} x_n = x_0 + \frac{nm}{\text{gcd}(a, m)} \; ( \text{mod} \; m) \qquad \text{for }n= 1, 2, \ldots , \text{gcd} (a, m) - 1. \end{equation*}