1

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

Bill Dubuque
  • 272,048
aneorddot
  • 97

4 Answers4

3

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

André Nicolas
  • 507,029
  • 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 05 '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 05 '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 05 '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 05 '14 at 17:18
1

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

Bill Dubuque
  • 272,048
0

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

John Machacek
  • 2,976
0

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

alans
  • 6,475