$$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?
Best Answer
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