Congruence rules when solving equation

Question

I am trying to solve the following congruence problem.

980x ≡ 1500 mod 1600

The steps I came up with were as follows:

1. 980x ≡ 1500 mod 1600
2. 49x ≡ 75 mod 80 (Divide by 20, gcd(20, 1600) = 20 so 80 = 1600/20)
3. 98x ≡ 150 mod 80 (Multiply both sides by 2)
4. 18x ≡ 70 mod 80 (Simplify)
5. 90x ≡ 350 mod 80 (Multiply both sides by 5)
6. 10x = 30 mod 80 (Simplify)
7. x = 3 mod 8 (Divide by 10, gcd(10, 80) = 10, so 8 = 80/10)

However, this answer does not satisfy the original equation. Which steps are incorrect and is there a simpler way to approach this other than decomposing into diophantine equations?

Thanks

Answer 1

We need to find $x\pmod{80}$ for $49x=80y+75$ where $y$ is any integer

$49x=5(16y+15)\implies5|x,x=5z$(say)

$\implies49(5z)=5(16y+15)\iff49z=16y+15\iff z=16(y-3z)+15$

$x=5z=80(y-3z)+75\equiv75\pmod{80}$

---

Alternatively,

$49x\equiv75\pmod{80}=80a+75=5(16a+15)$ where $a$ is any integer

$\implies5|x$ let $x=5y\implies49(5y)\equiv75\pmod{80}\iff49y\equiv15\pmod{16}$

As $49\equiv1\pmod{16},y\equiv15\implies x=5y\equiv75\pmod{80}$

Answer 2

As Macavity said in his comment, when you multiplied by something that was not coprime to your modulus, you introduced extra solutions. Indeed, following your logic from number $2$, equation $3$ could be reduced to $49x\equiv75\pmod{40}$.

$49$ does not have an obvious inverse mod $80$. However, if you look at the problem mod $5$ and mod $16$, the solution becomes very simple.

$$x\equiv-5\pmod{16}$$ $$-x\equiv0\pmod 5$$

What number is a multiple of $5$ and $5$ less than a multiple of $16$? Clearly, it's $-5$.