2
$\begingroup$

I am having a problem when the LHS has an addition function; if the question is just a multiple of $x$ it's fine.

But when I have questions like $3x+3$ or $4x+7$, I don't seem to get the right answer at the end.

$\endgroup$
  • 1
    $\begingroup$ Are you sure you're not overlooking just moving the $3$ over? $\endgroup$ – Andrew Chin Oct 3 at 16:39
  • $\begingroup$ yeah thought of that obviously but didn't know how to treat a negative mod, but now I know. Thanks, mate!!! $\endgroup$ – Charan Presence Oct 3 at 16:45
  • $\begingroup$ Welcome to Mathematics Stack Exchange. How would you solve $7x+3=1$ where $x$ is a real number? $\endgroup$ – J. W. Tanner Oct 4 at 7:43
2
$\begingroup$

We have that

$$7x + 3 \equiv 1 \mod 31 \implies 7x\equiv -2\mod 31$$

Then we need to evaluate by Euclidean algorithm the inverse of $7 \mod 31$, that is

  • $31=4\cdot \color{red}7 +\color{blue}3$

  • $\color{red}7=2\cdot \color{blue}3 +1$

then

  • $1=7-2\cdot 3=7-2\cdot (31-4\cdot 7)=-2\cdot 31+9\cdot 7$

that is $9\cdot 7\equiv 1 \mod 31$ and then

$$9\cdot 7x\equiv 9\cdot -2\mod 31 \implies x\equiv 13 \mod 31$$

$\endgroup$
1
$\begingroup$

Hint: The congruence $7x+3\equiv 1\mod 31$ is the same as $7x\equiv -2\mod 31$ with $-2\equiv 29\mod 31$. Compute the inverse of $7\mod 31$ using the extended Euclidean algorithm. Then $x\equiv 7^{-1}\cdot 29\mod 31$.

$\endgroup$
  • $\begingroup$ Thank you so much, I just started learning this concept so a bit weak in the basics. The answer checks out CHEERS!!! $\endgroup$ – Charan Presence Oct 3 at 16:45
0
$\begingroup$

$7x+3\equiv1\implies7x\equiv1-3=-2\equiv29\equiv60\equiv91\implies x\equiv13\pmod {31}.$

$\endgroup$
0
$\begingroup$

By Gauss's algorithm $\bmod 31\!:\,\ 7x\equiv -2\iff x\equiv \dfrac{-2}7\equiv\dfrac{-8}{28}\equiv\dfrac{-39}{-3}\equiv \,\bbox[5px,border:1px solid #c00]{13}$


Or by Inverse Reciprocity

$\bmod 31\!:\,\ \dfrac{-2}{7}\equiv \dfrac{-2-31\!\!\!\!\overbrace{\left[\dfrac{-2}{\color{}{31}}\bmod 7\right]}^{\large -2/3\,\equiv\,-9/3 \,\equiv\, \color{#c00}{-3\ }}}7\equiv\dfrac{-2-31[\color{#c00}{-3}]}7\equiv\dfrac{91}7\equiv\,\bbox[5px,border:1px solid #c00]{13}$


Or by the forward extended Euclidean Algorithm (and its fractional form)

$\ \ \ \ \begin{array}{rr} [\![1]\!] &31\, x\,\equiv\ 0 \\ [\![2]\!] &\ \color{#0a0}{7\,x\, \equiv -2}\!\!\!\\ [\![1]\!]-4\,[\![2]\!] \rightarrow [\![3]\!] & 3\,x\, \equiv\, 8 \\ [\![2]\!]-2\,[\![3]\!] \rightarrow [\![4]\!] & \bbox[5px,border:1px solid #c00]{x\, \equiv -18}\!\!\!\!\!\!\!\! \end{array}$

said multi-fractionally $\ \ \dfrac{0}{31} \overset{\large\frown}\equiv \color{#0a0}{\dfrac{-2}7} \overset{\large\frown}\equiv \dfrac{8}3 \overset{\large\frown}\equiv\,\bbox[5px,border:1px solid #c00]{\dfrac{-18}1}\ $ $\ \leftarrow\ \text{easiest } {\it general }\ \text{ method}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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