4

$$2842x \equiv 1547 \pmod{103} $$

How can I simplify this? $GCD(2842,103)=1$, so my guess would be to divide the equation by 7, which is the $GCD$ of 2842 and 1547. So:

$$406x \equiv 221 \pmod{103}$$

Ok, it looks a little bit simpler now.

However I've heard that the $61x \equiv 2 \pmod{103}$ equation is equal to the topmost equation here. But how is this possible? Is it? And if so, why is that so?

khernik
  • 1,369

1 Answers1

2

As $2842\equiv61\pmod {103}$

and $1547\equiv2\pmod {103}$

Alternatively, $2847x\equiv1547\pmod{103}$ $\implies 2847x=1547+103y$ for some integer $y$

As $2842=27\cdot103+61$ and $1547=15\cdot103+2$

we can write $(27\cdot103+61)x=15\cdot103+2+103y$

$\implies 61x=2+103(y-27x-15)\equiv2\pmod {103}$ as $y-27x-15$ is an integer as $x,y$ are integers

lab bhattacharjee
  • 274,582