3
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by Dietrich Burde, José Carlos Santos, ancientmathematician, Namaste, kjetil b halvorsen Dec 15 '18 at 17:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ 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. $\endgroup$ – Dietrich Burde Dec 15 '18 at 9:15
  • $\begingroup$ 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. $\endgroup$ – thesagniksaha Dec 15 '18 at 9:22
  • $\begingroup$ math.stackexchange.com/questions/3040108/… $\endgroup$ – lab bhattacharjee Dec 15 '18 at 9:27
  • $\begingroup$ 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). $\endgroup$ – user21820 Dec 15 '18 at 17:49
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. I understand that it better now. $\endgroup$ – Dan Dec 15 '18 at 22:19
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. This helps a lot. $\endgroup$ – Dan Dec 15 '18 at 22:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.