# A problem in linear congruences equation

I have solved a pair of linear congruence equations like $$x\equiv2\pmod {5}$$$$x\equiv4\pmod{7}$$

But now it is difficult for me to solve $$71x\equiv26\pmod {238}$$

Even I'm not able to think how can I start for this problem.

Please provide a hint so that I can begin it and proceed for its solution

Multiply both sides of the congruence by $71^{-1}$ (mod $238$)

• Sorry @pwerth but I'm a beginner in congruences ( I have started solving congruences one hour ago),, so can you help me a little further???,, because I don't know how to deal with inverse of modulars May 22 '17 at 21:33
• You can use the Euclidean algorithm to find the inverse. If this is unfamiliar, do some Googling. For example check out: math.utah.edu/~fguevara/ACCESS2013/Euclid.pdf May 22 '17 at 21:36
• That was very useful@pwerth , thanks for your help May 22 '17 at 21:39

Factorisation of $\quad 238=2\times 7\times 17$

$\begin{cases} 71\equiv 1\pmod 2\\ 71\equiv 1\pmod 7\\ 71^{16}\equiv 1\pmod {17} & \text{by little fermat theorem}\\ \end{cases}$

So by Chinese remainder theorem $71^{16}\equiv 1\pmod{238}$

It ensue that $71^{-1}\equiv 71^{15}\equiv 57 \pmod{238}$

Thus $x\equiv 57\times 26\equiv 54\pmod{238}$

• Nice answer,, after understanding chinese remainder theorem May 25 '17 at 17:27

HINT

In order to solve this linear congruence, you first need to find what is called a multiplicative inverse of the integer $71$ modulo $238$.

What is that?  Well, it's an integer that when $71$ (mod $238$) is multiplied by it, you get $1$ (mod $238$).

So, if we say  $u$  is a multiplicative inverse of $71$ (mod $238$), then $71u$ $\equiv 1$ (mod $238$).



Stop reading here if you want to give it a try yourself.



Now, to find a value for $u$, I applied a method called Euclid's algorithm (you can google it to learn how it works), which gave the value $57$.

So, $57$ is a multiplicative inverse of $71$ modulo $238$.  This makes sense because,

$71 \times 57 \equiv 4047 \equiv 17\times 238+1 \equiv 1$ (mod $238$).

Applying this to your congruence, we have

$71x \equiv 26$ (mod $238$)

$57\times 71x \equiv 57\times26$ (mod $238$)

$1\times x \equiv 1482$ (mod $238$)

$x \equiv 6\times 238 + 54$ (mod $238$)

$x \equiv 54$ (mod $238$),

as required.