How to solve $42x = 47 \pmod{101}$?

Question

Does anyone know how I can solve this question?
Since $101$ is a prime number, I can't figure out where to begin. $$x = \frac{47}{42} \pmod{101} \ldots ?$$

Thanks!

Answer 1

Using $a\equiv101-a\pmod{101}$ you get $$42x\equiv-54\pmod{101}$$ Now dividing by $6$ (we can because $\gcd(6,101)=1$) we get $$7x\equiv-9\pmod{101}\\-94x\equiv 92\pmod{101}\\-47x\equiv 46\pmod{101}\\54x\equiv 46\pmod{101}\\27x\equiv 23\pmod{101}\\27x\equiv-78\pmod{101}\\9x\equiv-26\pmod{101}\\9x\equiv 75\pmod{101}\\3x\equiv 25\pmod{101}$$ Now since for $x=34$ we have $3x\equiv 1\pmod{101}$ then for $x=34\cdot 25$ we have $3x\equiv 25\pmod{101}$ while $34\cdot 25=17\cdot 50=850$ and $850\equiv 42\pmod{101}$ hence $x\equiv 42\pmod{101}$ is the solution to $42x\equiv 47\pmod{101}$

Answer 2

Hint: Use the extended Euclidean algorithm for $\gcd(42,101)$ to find $a$ such that $42a \equiv 1 \bmod 101$.

Alternatively, note that $42= 2 \cdot 3 \cdot 7$ and find the inverses of $2,3,7 \bmod 101$, which are probably easy by inspection.

Answer 3

Hint. By using the Euclidean algorithm, find two integers $a$ and $b$ such that $$42a-101b=1.$$ Then $$47a=(42a)x=(1+101b)x\equiv x \pmod{101}.$$

Answer 4

HINT: use that $$42\cdot 42=1764=17\cdot 101 +47$$

Answer 5

Your equation is equivalent to find to integers $x,k$ such that $$42x + 101k = 47.$$ Using Euclid's algorithm: $$101 = 42\cdot 2+17$$ $$42 = 17\cdot2+8$$ $$17 = 8\cdot2+1$$ which gives $$1 = 101\cdot5+42\cdot(-12).$$ Now multiply by $47$: $$47 = 101(235)+42(-564).$$ So $x = -564 \mod 101 = 42 \mod 101.$

Answer 6

$$42x = 47 \pmod{101} \implies (42x + 47) \equiv 0 \pmod{101}$$ This implies that

$$101\,\big|\,42\cdot x\,$$ Therefore

$$x = \{101\cdot a \, \big| \,\forall\, a \in \mathbb{Z}\}$$