0
$\begingroup$

Find all solutions $x \in \mathbb{Z}_{m}$ of the following congruence, whereby $m$ is the modulus. If there isn't a solution, state why. $$52x \equiv 15 (\text{ mod } 91)$$

I'm not sure how to solve it because if we look at $52$ and $91$, we see that they aren't coprime. So we cannot use euclidean algorithm to continue because we haven't got $\text{gcd }(52,91)=1$.

Does that mean that there won't exist a solution? Or there is another way of solving it?

$\endgroup$
  • $\begingroup$ I am guessing you mean $\;m=91\;$ , but then there is no point in writing it that way, imo. $\endgroup$ – DonAntonio Nov 13 '16 at 13:38
  • 1
    $\begingroup$ Since 91 is not prime, one approach is to solve the congruence modulo its prime power factors, then piece those solutions together. $\endgroup$ – hardmath Nov 13 '16 at 13:39
5
$\begingroup$

Hints:

Fill in details

$$52x=15+91k\;,\;\;k\in\Bbb Z\implies15=13(4x-7k)$$

So how many solutions can you find?

$\endgroup$
  • $\begingroup$ I think there won't be a way that this will equal $15$; so no solutions? $\endgroup$ – berndgr Nov 13 '16 at 13:42
  • $\begingroup$ @berndgr Exactly. And there won't be solutions because both factors in the rightmost expression are integers... $\endgroup$ – DonAntonio Nov 13 '16 at 13:43
  • $\begingroup$ Awesome, thanks a lot! Glad to see it can be that easy without this annoying euclid. $\endgroup$ – berndgr Nov 13 '16 at 13:44
3
$\begingroup$

Note that $\gcd(52,91)=13$. Now reduce the congruence modulo $13$ (which is possible because $13$ divides $91$) to get $0x\equiv2\pmod{13}$; this has no solutions.

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