0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ May 22 '17 at 21:33
  • $\begingroup$ 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 $\endgroup$
    – pwerth
    May 22 '17 at 21:36
  • $\begingroup$ That was very useful@pwerth , thanks for your help $\endgroup$ May 22 '17 at 21:39
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nice answer,, after understanding chinese remainder theorem $\endgroup$ May 25 '17 at 17:27
1
$\begingroup$

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.


$ $

FULL ANSWER

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.

$\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.