0

Shortcut for solving $165x \equiv 100 \pmod{285}$

The usual way is to check values of x, but if a shortcut is needed then it is needed to convert the equation into an equality:
$165x = 100 + 285k, \exists k \in \mathbb{Z}$

This brings up a linear Diophantine equation (LDE) with $\gcd$ on r.h.s.
$165x -285k = 100$
=> $33x - 57k = 20$

Comparison with the standard form for LDE : $ax + by = c$
brings up the values of coefficients as : $a = 33, b = -57, c = 20$, with the values $x,y$ found by EEA.

Stuck here, please help.

jiten
  • 4,524
  • 1
    This has no solution. Note that $3$ divides both $285$ and $165$ but it does not divide $100$. – lulu Jan 18 '18 at 21:46
  • 2
    Since $\gcd(165, 285) = 15$ you are not going to get an $x$ that will give you $100$ – Doug M Jan 18 '18 at 21:46
  • Yes, r.h.s. in L.D.E. has to be a multiple of the g.c.d., i.e., here of the form : $15k, \exists k \in \mathbb{Z}$. – jiten Jan 18 '18 at 21:54

1 Answers1

1

Making use of Diophantine’s equation, \begin{align} -57 & = (-2)\times33 + 9\\ 33 & = 3\times 9 + 6 \\ 9 & = 1\times 6 + 3 \\ 6 & = 2\times 3 + 0 \end{align}

Since $20$ is not divisible by $3$, we have no solution.

Math Lover
  • 15,153
QuIcKmAtHs
  • 1,451