# Modular Arithmatic - Solving congruences

I'm sure this is pretty basic but I'm struggling to understand how to go about solving this problem for my homework. The question states "Solve the following congruences for x". The first problem is $2x+1\equiv 4\pmod 5$.

-
Have you studied modular inverses, and how to compute them? – Bill Dubuque Jul 5 '14 at 16:47
Probably about 100 years ago... :) Are modular inverses key to solving these types of problems? If so, I can start studying them! – aneorddot Jul 5 '14 at 17:01
Yes, if you wish to learn how to solve linear modular equations (congruences) then you should learn about modular inverses. See any textbook on elementary number theory. – Bill Dubuque Jul 5 '14 at 17:11
@Zlatan Please be more careful with your edits (which changed the modulus) – Bill Dubuque Jul 5 '14 at 17:11
@BillDubuque thank you, I'll look it up now as I see JMac31 referenced inverses below. – aneorddot Jul 5 '14 at 17:16

There are many ways to solve the problem. The conceptually simplest, but most tedious, is to test one by one the possibilities $x\equiv 0\pmod{5}$, $x\equiv 1\pmod{5}$, and so on up to $x\equiv 4\pmod{5}$. Quickly we find that $x\equiv 4\pmod{5}$. (This approach would become quite unpleasant if $5$ were replaced by $97$.)

It is simpler to use some algebra. So rewrite as $2x\equiv 3\pmod{5}$. Since $3\equiv 8\pmod{5}$, it is convenient to rewrite the congruence as $2x\equiv 8\pmod{5}$. Then since $2$ and $5$ are relatively prime, we can divide by $2$, getting $x\equiv 4\pmod{5}$.

A fancier version is to start from $2x\equiv 3\pmod{5}$. Now multiply both sides by $3$ (the modular inverse of $2$). We get $6x\equiv 9\pmod{5}$. But $6\equiv 1\pmod{5}$ and $9\equiv 4\pmod{5}$, so we conclude that $x\equiv 4\pmod{5}$.

Remark: We used congruence notation throughout, since it is very important to get accustomed to it. But $2x\equiv 3\pmod{5}$ means that $5$ divides $2x-3$. So we want to solve $2x-3=5k$, that is, $2x=3+5k$. So we want to find a $k$ such that $3+5k$ is divisible by $2$. It is clear that $k=1$ works, giving $2x=8$ so $x=4$. Any number congruent to $4$ modulo $5$ will also work, giving answer $x\equiv 4\pmod{5}$.

-
Okay, your remark clarification helped clear up where I was missing the point. It seems simple right now because like you said it's mod 5. If the mod 5 were replaced with a larger number, the same concept works, correct? Would there ever be a case where there's more than one value of x? – aneorddot Jul 5 '14 at 17:07
Yes, it can happen that there are no solutions, or several solutions. The issue arises when we are looking at $ax\equiv b\pmod{m}$, where $a$ and $m$ are not relatively prime. For example, look at the congruence $4x\equiv 0\pmod{8}$. This has $4$ solutions modulo $8$, namely $x\equiv 0\pmod{8}$, $x\equiv 2$, $x\equiv 4$, and $x\equiv 6$. However, when $a$ and $m$ are relatively prime, there is always a unique (modulo $m$) solution of the linear congruence $ax\equiv b\pmod{m}$. – André Nicolas Jul 5 '14 at 17:11
Okay, so first step would be to determine whether a and m are relatively prime. If they are, then I know I'm only looking for one solution. If they are not, then I know there are either no solutions or multiple solutions. Thank you for your help! – aneorddot Jul 5 '14 at 17:14
You are welcome. For large $m$, and $a$ relatively prime to $m$, the modular inverse approach is probably best, with the modular inverse of $a$ computed using the Extended Euclidean Algorithm. But at this early stage, the exercises are for getting familiarization with the congruence notation. – André Nicolas Jul 5 '14 at 17:18

Hint $\ {\rm mod}\,\ 2k\!-\!1\!:\,\ 2k\!-\!1\equiv 0\,\Rightarrow\, \color{#c00}{2k\equiv 1},\$ so $\, k\equiv 2^{-1}.\,$ Therefore, as usual, we can solve

the linear equation $\ 2x\equiv b\$ by scaling it by $\, 2^{-1}\equiv k\,$ to get $\, x\equiv (\color{#c00}{2k})x \equiv kb.$

-

Solve it like you would any linear equation expect you figure out what is $2^{-1}$ the multiplicative inverse of $2 \pmod 5$. That is find $a$ such that $2a \equiv 1 \pmod 5$.

-

By multiplaying with 3, we get: $$6x+3=12\mod 5,$$ from were is: $$x=9 \mod 5=4\mod 5$$.

-