1
$\begingroup$

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

$\endgroup$
2
  • 4
    $\begingroup$ By using the Euclidean algorithm backwards, you can find $y$ such that $46y\equiv 1\pmod{111}$ $\endgroup$ – Emre May 18 '16 at 7:37
  • 1
    $\begingroup$ $x=\frac {111n+15}{46} $. Find the diophantine equation for n when the numerator is 0 mod 46 $\endgroup$ – N.S.JOHN May 18 '16 at 7:39
2
$\begingroup$

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

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