# Find all solutions of the following congurence: $52x \equiv 15 (\text{ mod } 91)$

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?

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

Hints:

Fill in details

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

So how many solutions can you find?

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

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.