1
$\begingroup$

I got two questions that im wondering, one main question and one "bonus" question I guess

1) what is the general method to solve congruence equations like ax ≡ b (mod m) ?

take for example 3x≡2 (mod 5) how would I go about solving this?

I was able to solve it using trial and error and found the answer to be 4, but Im looking for a better and faster way to solve problems like these for larger m 's..

also im wondering sometimes you can solve these with just the inverse of a, but when does that apply? only when b=1 and a and m are coprime? example 9x≡1 (mod 14) for instance?

2) can someone please show me how I can find the modular inverse of 9 in mod14 ?, im familiar with the method used and Im able to find the inverse in other examples, but im not sure why this one is casuing me so much trouble, answer should be 11 I think

$\endgroup$
  • 1
    $\begingroup$ 1) Euclidean algorithm is the way to go for bigger $m$. When $m$ is small its faster to brute force every possibility. And if you have the inverse of $a$ you can always just multiply with that to get the solution. 2) Solve $9x=1$ (mod $14$) to get the inverse. $\endgroup$ – Harto Saarinen Nov 26 '15 at 21:30
  • $\begingroup$ ok so for 1) I just try to find the inverse and multiply thats it? 2) thats exactly what I wasnt able to do btw..dunno why that one caused so much problem for me, probably just some silly mistake, but I looked through it and tried again several times still dont get the correct answer. @HartoSaarinen $\endgroup$ – eyy321 Nov 26 '15 at 21:34
  • 2
    $\begingroup$ Inverses can always solve $ax\equiv b\pmod{m}$ when $\gcd(a,m)$. The solution is $x\equiv ba^{-1}\pmod{m}$. $\endgroup$ – user236182 Nov 26 '15 at 21:34
  • 1
    $\begingroup$ Finding $9^{-1}\bmod 14$ is equivalent to solving $9x\equiv 1\pmod{14}$. You can use Extended Euclidean Algorithm to find $s,t$ such that $9s+14t=1$. Then $x\equiv s\pmod{14}$. Or notice that $$9x\equiv 1\equiv -27\pmod{14}\stackrel{:9}\iff x\equiv -3\equiv 11\pmod{14}$$ $\endgroup$ – user236182 Nov 26 '15 at 21:38
  • 1
    $\begingroup$ @eyy321 $ax\equiv b\pmod{m}$ has a solution if and only if $\gcd(a,m)\mid b$. So $ax\equiv \gcd(a,m)k\pmod{m}$ has a solution for any integers $a,m,k$, even if $\gcd(a,m)>1$. $\endgroup$ – user236182 Nov 26 '15 at 21:52
1
$\begingroup$

A few methods to solve $ax\equiv b\pmod{m}$:

$1)\ $ Checking $x\equiv \{0,1,2,\ldots,m-1\}\pmod{m}$, i.e. using brute force.

$2)\ $ Doing something similar to this: $$3x\equiv 2\equiv -3\pmod{5}\stackrel{3}\iff x\equiv -1\equiv 4\pmod{5}$$

$$9x\equiv 1\equiv -27\pmod{14}\stackrel{:9}\iff x\equiv -3\equiv 11\pmod{14}$$

$3)\ $ Using inverses / Extended Euclidean Algorithm.

Inverses can always solve $ax\equiv b\pmod{m}$ when $\gcd(a,m)$. The solution is $x\equiv ba^{-1}\pmod{m}$.

You can find $a^{-1}\bmod m$ by either using Extended Euclidean Algorithm or solving $ax\equiv 1\pmod{m}$.

Using Extended Euclidean Algorithm:

$$\begin{array}\\14=14(1)+9(0)\\ 9=14(0)+9(1)\\ 5=14(1)+9(-1)\\4=14(-1)+9(2)\\1=14(2)+9(-3)\end{array}$$

Therefore $9^{-1}\equiv -3\equiv 11\pmod{14}$.


As for your comment: $ax\equiv b\pmod{m}$ has a solution if and only if $\gcd(a,m)\mid b$. This follows from Bézout's Lemma.

$\endgroup$
1
$\begingroup$

For 1): if $a$ and $m$ are coprime, the extended Euclidean algorithm gives you an automatic way to find the coeffcicients of a Bézout's relation: $$ua+vm=1,\quad \lvert u\rvert<m,\enspace\lvert v\rvert< a$$ This Bézout's relation tells you $u$ is a modular inverse of $a$, hence $$ax\equiv b\mod m\iff uax\equiv ub\mod m\iff x\equiv ub\mod m. $$

If $a$ and $m$ are not coprime, let $d=\gcd(a,m)$ and write $\;a=da'$, $m=dm'$ ($\gcd(a',m')=1$). The equation writes as $$da'x\equiv b\mod dm',$$ and it has no solution if $b\not\equiv 0\mod d$. If $b=db'$, it is equivalent to $$a'x\equiv b'\mod m',$$ and we're back to the first case.

For 2), a Bézout's relation between $9$ and $14$ is $2\cdot 14-3\cdot 9=1$, hence $$9^{-1}\equiv -3\equiv 11\mod 14. $$

$\endgroup$
0
$\begingroup$

1) $6\equiv1\mod5$ and thus $3*2\equiv1 \mod 5$ is the "inspection" route one could take there.

For, $9x\equiv1\mod14$, I could consider how $9\equiv-5\mod14$ where $-5*3\equiv-15\equiv-1\mod14$, so $3*9$ will give me a -1 so add another 3 and 9 together so that $9*3*3\equiv81\equiv11$ (14*5=70 would be the shortcut to see here) would seem to be the inverse which could be trimmed down by casting out 14s if doing this programmatically.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.