0

I am trying to solve

$bx \equiv a \pmod p$

Where a,b,p is known and p is a prime. For example:

$14x \equiv 1 \pmod p \implies x = 4$

Is there an efficient algorithm to solve this equivalance? I feel a bit daft for asking this as I think I should know the answer but I never properly got into modular arithmetics while studying.

PS. It's related to cryptography so a,b and p can be quite large

Just another metaprogrammer
  • 123
  • 1
    Recall that $b$ has an inverse mod p? This means that there exists some integer $n$ with $1 \leq n < p$ such that $bn \equiv 1 \pmod{p}$. So multiply by that inverse on both sides of the congruence. The inverse can be found either by inspection or by applying the Euclidean algorithm as the answers below show. – Numbersandsoon Oct 19 '13 at 22:49
  • Thanks for all the suggestions, I will try the suggestions later tonight. – Just another metaprogrammer Oct 21 '13 at 13:08

4 Answers4

3

First of all you need to check wheter there is a solution. First find $d = gcd(b,p)$ if it's 1, then we'll always have solution. Otherwise in order to have solution $a$ need to be divisible by $d$. Note that you need to make $a + np$ for some integer $n$ divisibly by $d$.

But because the modulo is prime, you'll get that $d$ is either $1$ or $p$. So if $d=p$ then the equation will have a solution for $a=0$ and the solution will be every integer $x$

Once you've done that Euclidean Algorithm is the way to go here, because all you need to do is follow the rules, i.e. everything you do is according to the book.

Another useful method is the Gauss Method. It's simplier and probably faster than the Euicliden Algorithm (especially for smaller moduli), but you need a little bit of creativity and rational reasoning. The idea is to bring the fraction $\frac{a}{b}$ to a integer using multiplication, division and modular arithemtics.

You need to multiply or divide both numerator and denominator, but be careful not to multiply or divide with divisors of the modulo. Also you can take modulo values. Do this until you get a integer value. For example let $p=5$ we have:

$$\frac 1{14} \times \frac 44 = \frac 4{56} = \frac{4}{1}$$

So this means that $x \equiv 4 \pmod {5}$

But sometimes, especially for larger moduli this calculation will seem like it'll go to infinity, without any result. But if there exist a solution for $x$ you should be able to find it.

Stefan4024
  • 35,843
2

I assume you know that $b$ is not divisible by $p$. Use the Euclidean algorithm to find integers $m$ and $n$ such that $$mp+nb=1.$$ Thus $nb \equiv 1 \pmod{p}$. Your answer is then $x \equiv na \pmod{p}$, or if you like, just $x=na$. The Euclidean algorithm is very efficient! And note that if $p$ divides $b$ then the problem is trivial.

TBrendle
  • 3,253
1

The integers modulo a prime $p$ form field. Prove that.

Now if $b = 0$, then $a$ must equal zero as well for their to be a solution, and in that case all $x \in \Bbb{Z}_p$ are solutions, or all $x \in \Bbb{Z}$, however you want to look at it. If $b \neq 0$, then since $\Bbb{Z}_p$ is a field, there exists $b^{-1}$, a multiplicative inverse of $b$. Then $x = b^{-1} a$ is the single solution $\pmod p$. However, all integers that are congruent to $b^{-1}a \pmod p$ are all the solutions in $\Bbb{Z}$.

Daniel Donnelly
  • 21,342
1

You apply extended Euclidean Algorithm to (b,p) then you will find $(m,n)$ such that $mp+nb=1$ then muiltiply with $a$ and you get $mpa+nba=a$ then take $\mod p$ and you get the solution $x\equiv na (\mod p).$

111
  • 747