Solving for a variable in a modular arithmetic equation

Question

$\fbox{$13x + 1 \equiv 0 \pmod {100}$}$

I solved the equation above by trying different multiples to isolate $x$ until I found something that worked. I have two questions:

$\fbox{$1.$}\ $ What if there was no solution for $x$? How would I be able to prove it?

$\fbox{$2.$}\ $ Are there a set of steps that I could program a computer to follow and get an answer if other similar modular equations are inputted?

My solution is below:

$13x +1 \equiv 0 \pmod {100}$

$13x \equiv 99 \pmod {100}$ (added $99$ to both of equation and applied the $\mod 100$ to the left side)

$104x \equiv 792 \pmod {100}$ (multiplied both sides by $8$)

$4x \equiv 792 \pmod {100}$ (removed a $100$ from the left side)

$x \equiv 198 \pmod {100}$ (divided both side by $4$)

Like I said, I believe I got the right solution but only through trial and error. I was wondering if there is a more systematic way of solving these problems.

Thank you for any help.

Answer 1

Writing $$x\equiv -\frac{1}{13}\mod 100$$ adding the module to the numerator we get $$x\equiv \frac {99}{13}\equiv \frac{199}{13}\equiv \frac{299}{13}\equiv 23\mod 100$$ so $$x\equiv 23\mod 100$$

Answer 2

This is equivalent to the congruence equation $$13x\equiv -1\mod 100,$$ so you only have to find an inverse of $13\bmod 100$. As $13$ and $100$ are coprime, this inverse exists by Bézout's identity (this answers negatively your first question). You'll find it with the extended Euclidean algorithm: \begin{array}{rrrl} r_i & u_i & v_i & q_i \\\hline 100 & 0 & 1 \\ 13 & 1 & 0 & 7 \\\hline 9 & -7 & 1 & 1 \\ 4 & 8 & -1 & 2 \\ 1 & \color{red}{-23} & 3 \\ \hline \end{array}

Thus the inverse of $13$ is $-23$, and $$13x\equiv -1\mod 100\iff x\equiv(-23)(-1)= 23\mod 100.$$