Simple mod problem

Question

It’s kind of a silly question but I can't find a simple way for finding the value of variable $d$ .

$(5*d) \mod 8 = 1$

I normally just do this recursively by saying $d=d+1$ until I get the right answer. Is there a better way of solving this?

Answer 1

5(5)-3(8)=1 and take mod 8 to get the answer 5

Answer 2

$5d=8k+1$

$d=\frac{8k+1}{5}$

Choose $k=3$ obviously, and you'd get $d=5$.

To verify,

$5\times5\ (mod\ 8)=25\ (mod\ 8)=1$

Answer 3

I guess the easiest way is by demanding that $5*d = 8*a + 1 $. Since $8*5$ is zero under $mod 8$, You only need to check the values $1,\cdots 7$.

Answer 4

To find the multiplicative inverse of $5$ modulo $8$, use the Extended Euclidean Algorithm.

First, solve for the greatest common divisor of $5$ and $8$, which is $1$ since they are relatively prime. \begin{align*} 8 & = 1 \cdot 5 + 3\\ 5 & = 1 \cdot 3 + 2\\ 3 & = 1 \cdot 2 + 1\\ 2 & = 2 \cdot 1 \end{align*} Now, work backwards to solve for $1$ as a linear combination of $5$ and $8$. \begin{align*} 1 & = 3 - 2\\ & = 3 - (5 - 3)\\ & = 2 \cdot 3 - 5\\ & = 2 \cdot (8 - 5) - 5\\ & = 2 \cdot 8 - 3 \cdot 5 \end{align*} Since $2 \cdot 8 - 3 \cdot 5 = 1$, $-3 \cdot 5 = 1 + 2 \cdot 8$, so $$-3 \cdot 5 \equiv 1 \pmod{8}$$ Hence, $-3$ is in the residue class of the multiplicative inverse of $5$ modulo $8$. To express the multiplicative inverse as one of the residues $\{0, 1, 2, 3, 4, 5, 6, 7\}$, we add $8$ to $-3$ to obtain $5$. Thus, $5$ is the multiplicative inverse of $5 \pmod{8}$.

Check: $5 \cdot 5 \equiv 25 \equiv 1 + 3 \cdot 8 \equiv 1 \pmod{8}$.