How would you solve this modular equation without being able to find the multiplicative inverse?

Question

If I have $15a \equiv 60 \space mod \space 95$, how could I solve for $a$? The equation has multiple solutions (23 and 42 among them) -- how do I find them without resorting to guess-and-check?

Answer 1

Since $5$ divides all of $15$, $60$, and $95$, we have $15x\equiv 60\pmod{95}$ if and only if $3x\equiv 12\pmod{19}$.

And since $3$ is relatively prime to $19$, the second congruence holds if and only if $x\equiv 4\pmod{19}$.

The above is a complete answer. But if you want to give the answers modulo $95$, we have $x\equiv 4$, $23$, $42$, $61$, or $78$ modulo $95$.

Remark: After we reached $3x\equiv 12\pmod{19}$, we could have travelled through the modular inverse route, but ordinary division by $3$ is faster.