Solve $276 x\equiv 90\pmod {666}$

Question

Solve $276 x\equiv 90\pmod {666}$

I found using Euclidean algorithm that $\gcd (276,666)=6$

then I divided by $6$ and I got:

$$46x\equiv 15\pmod {111}$$

and I found that $\gcd(46,111)=1$ using Euclidean algorithm

I am stuck here and don't know what to do

Answer 1

You correctly reduced the problem to $46x \equiv 15 \pmod{111}$. Applying the Euclidean algorithm to find $\gcd(46, 111)$ yields \begin{align*} 111 & = 2 \cdot 46 + 19\\ 46 & = 2 \cdot 19 + 8\\ 19 & = 2 \cdot 8 + 3\\ 8 & = 2 \cdot 3 + 2\\ 3 & = 1 \cdot 2 + 1\\ 2 & = 2 \cdot 1 \end{align*} so $\gcd(46, 111) = 1$ as you found.

We now follow E. Girgin's advice and apply the extended Euclidean algorithm to find the multiplicative inverse of $46$ modulo $111$. Working backwards to write $1$ as a linear combination of $46$ and $111$ yields \begin{align*} 1 & = 3 - 2\\ & = 3 - (8 - 2 \cdot 3)\\ & = 3 \cdot 3 - 8\\ & = 3(19 - 2 \cdot 8) - 8\\ & = 3 \cdot 19 - 7 \cdot 8\\ & = 3 \cdot 19 - 7(46 - 2 \cdot 19)\\ & = 17 \cdot 19 - 7 \cdot 46\\ & = 17(111 - 2 \cdot 46) - 7 \cdot 46\\ & = 17 \cdot 111 - 41 \cdot 46 \end{align*} Hence, $-41 \cdot 46 = 1 - 17 \cdot 111 \implies 46^{-1} \equiv -41 \equiv -41 + 111 \equiv 70 \pmod{111}$. Multiplying both sides of the equation $46x \equiv 15 \pmod{111}$ by $70$ yields \begin{align*} 70 \cdot 46x & \equiv 70 \cdot 15 \pmod{111}\\ x & \equiv 1050 \pmod{111}\\ x & \equiv 9 \cdot 111 + 51 \pmod{111}\\ x & \equiv 51 \pmod{111} \end{align*}