# How would I solve the following congruence?

$5x \equiv 118 (\mod 127)$

This is what I have done so far:

$127 = 25*5+2$

$2 = 127-25*5$

$25 = 12*2+1$

$1 = 25-12*2$

$1 = 25-12(127-25*5)$

I am a little stuck on how to continue.

I know I am supposed to write it in a form such that $5v+127w = 1$ but I am not exactly sure how I would do that.

Any help?

• 305 * 5 - 12 * 127 = 1 – stuart stevenson Jan 8 '18 at 23:46
• If you are ok, you can accept the answer and set as solved. Thanks! – user Jan 10 '18 at 23:37
• Please, if you are ok, you can accept the answer and set it as solved. Thanks! – user Feb 4 '18 at 0:05

## 8 Answers

Here's a quick way to solve this type of problem when the coefficient of x is small. 127 is a prime and 5 does not divide it, so keep adding 127 to the right hand side until you get something divisible by 5. (One of the first four sums must be.) As it happens 127+118=245, and 5x = 245 mod 127. Since 127 is a prime, we can cancel the factor of 5 and the solution is x = 49 mod 127.

Note that $51$ is the inverse of $5 \pmod {127}$ thus

$$5x \equiv 118 \pmod {127}\iff51\cdot5x\equiv x\equiv 51\cdot 118 \pmod {127}\iff x\equiv 49 \pmod {127}$$

$305\cdot 5 - 12\cdot 127 = 1$

$118\cdot 305\cdot 5 - 118\cdot 12\cdot 127 = 118$

$5\cdot 35990 \equiv 118 \pmod{127}$

Then subtract the biggest multiple of 127 less than 35990 which is $283\cdot 127 = 35941$

Therefore $x = 49 + 127a$ where $a$ is integer.

• Best to use $\cdot :\;$ \cdot instead of $*$. Also, using \pmod{127} yields $\pmod{127}$ – Namaste Jan 9 '18 at 0:03

To solve $5x \equiv 118 \mod 127$, first find the $\gcd$ of $5$ and $127$ using the Euclidean method. $$127 = 5 \times 25 + 2, 5 = 2 \times 2 + 1$$ this tells us the $\gcd$ is $1$. Furthermore: $$1 = 5 - 2 \times 2 = 5 - 2 \times (127 - 25 \times 5) = 5 - 2 \times 127 + 50 \times 5 = 51 \times 5 - 2 \times 127$$

therefore: $$118 = (51 \times 118) \times 5 - (2 \times 118) \times 127 \implies (51 \times 118) \times 5 \equiv 118 \mod 127$$ Therefore, $x = 51 \times 118$ does the job. Upon a little more simplification:$$51 \times 118 \equiv 51 \times -9 \equiv -459 \equiv 49 \mod 127$$

Indeed, $49 \times 5 = 245 \equiv 118 \mod 127$, so $x=49$ does the job.

EDIT : The general principle involved in solving this question is as follows : first find the gcd of the right hand coefficient and the modulus, using the extended Euclidean algorithm. Then, one can see that "reversing" the Euclidean procedure, as many others have shown here, actually gives you explicit coefficients with which the Bezout's identity is satisfied. If the right hand side of the congruence is a multiple of the $\gcd$ then multiply the earlier obtained Bezout identity by the appropriate quantity to obtain a unique solution. However, if that is not the case, then the congruence is not solvable (for example, $2x \equiv 1 \mod 4$).

\begin{align*} 1&=25-12(127-25\cdot 5)\\ &=25(1+12\cdot 5)-12(127)\\ &=25(61)-12(127)\\ &=5(305)-12(127) \end{align*}

Use the extended Euclidean algorithm: $$\begin{array}{c*{3}{c}} r_i&u_i&v_i&q_i \\ \hline 127&0&1\\ 5&1&0&25\\ 2& -25&1&2\\ \color{red}1&\color{red}{51}&-2\\ \hline \end{array}$$ Thus a Bézout's relation between $5$ and $127$ is $$51\cdot 5-2\cdot 127=1,$$ so $5^{-1}\bmod127\equiv 51$, and the solution is $$x\equiv5^{-1}\cdot118\equiv 51\cdot(-9)=-459\equiv 49\mod127.$$

Let us find the multiplicative inverse first - which is an integer $x$ such that $ax \equiv 1 \pmod m$. In our problem $a=5$, and $m = 127$, so we get $5x \equiv 1 \pmod {127}$.

When we subtract $127$ from multiples of $5$, we will get to $130-127$, which does not equal $1$. However, when we do the same to $2 \cdot 127$, or $254$, then we get $255-254 = 1$, which works! Therefore as $5x = 255$, $x = 51$.

Now when $5x \equiv 118 \pmod {127}$, $51*118$ is a solution to the congruence. Can you simplify this number $\pmod {127}$ and find $x$?

To solve it as a naive, start from your second line of solution: $$127-25 \times5=2 \tag{1}$$ Now$$118/2=59$$ Multiply (1) by 59:- $$59\times 127-5\times 1475=118$$ All the solutions will be of the form $$x=59+\frac{1475k}{1}\tag{2.}$$and $$y=-1475+\frac{59k}{1} \tag{3.}$$for $127x+5y=118$.
Or you can adopt extended euclidean algorithm to solve as shown in other answers.