# Solving for a variable in a modular arithmetic equation [duplicate]

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

## marked as duplicate by Dietrich Burde, José Carlos Santos, ancientmathematician, amWhy, kjetil b halvorsenDec 15 '18 at 17:48

• 1. Since $gcd(13,100)=1$ there are $x,y$ with $13x+100y=1$ (this is called the Bezout Lemma). Hence there is a solution. – Dietrich Burde Dec 15 '18 at 9:15
• For different modular equations, we can check if it holds certain modular properties or not to confirm the existence of solutions. Here, for example, the equation is $13x + 1 \equiv 0 \pmod{100}$ $\implies 13x \equiv -1 \pmod{100}$. Since $13$ is co-prime to $100$, it obliviously has a solution for $13x \equiv 1 \pmod{100}$ (existence of inverse). Replace $x$ with $-x$ and you're done. – thesagniksaha Dec 15 '18 at 9:22
• math.stackexchange.com/questions/3040108/… – lab bhattacharjee Dec 15 '18 at 9:27
• The current answers failed to point out that your attempt was completely incorrect. In particular, your last step (division by $4$) is invalid. Counter-example: $4·31 \equiv 24$ mod $100$ but $31 \not\equiv 6$ mod $100$. At one point you multiplied by $8$, which has a common factor with $100$, so it became irreversible (and the resulting equations have more solutions). – user21820 Dec 15 '18 at 17:49

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