x ≡ (mod )
A-CALCULATOR.COM

FAQs & How-to's

About This Calculator

  1. What is this calculator for?
  2. Can I embed this on my website?
  3. How can I do the math by hand?

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 can I do the math by hand?

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*}