Solve the following equation in $\mathbb{Z}_{16}$

Question

I have this equation $\hat{5}x = \hat{6}$ in $\mathbb{Z}_{16}$. I'm not good at all at modular arithemetic. So far I just figured it out that $\hat{5}x = 6+16k, k\in \mathbb{Z}$.

Answer 1

We can solve the congruence $5x \equiv 6 \pmod{16}$ by first finding the multiplicative inverse of $5$ in $\mathbb{Z}_{16}$ to determine the value of $x$ that satisfies the congruence $5x \equiv 1 \pmod{6}$, then multiplying both sides of the congruence by $6$.

Since $\gcd(5, 16) = 1$, $5$ has an inverse in $\mathbb{Z}_{16}$. We can find the inverse by applying the extended Euclidean algorithm.
$$16 = 3 \cdot 5 + 1$$ Solving for $1$ yields $$1 = 16 - 3 \cdot 5$$ Hence, $$-3 \cdot 5 \equiv 1 \pmod{16}$$ Thus, $5^{-1} \equiv -3 \equiv -3 + 16 \equiv 13 \pmod{16}$, so we may write $$13 \cdot 5 \equiv 1 \pmod{16}$$ If we multiply both sides of the congruence by $6$, we obtain $$78 \cdot 5 \equiv 6 \pmod{16}$$ Since $78 \equiv 78 - 4 \cdot 16 \equiv 14 \pmod{16}$, we obtain $$14 \cdot 5 \equiv 6 \pmod{16}$$ Hence, the solution to the congruence $$5x \equiv 6 \pmod{16}$$
is $$x \equiv 14 \pmod{16}$$ Check: $5 \cdot 14 \equiv 70 \equiv 4 \cdot 16 + 6 \equiv 6 \pmod{16}$.

Answer 2

The basic procedure for solving linear modular equations in $\mathbb{Z}_{N}$ has the following form:

Suppose given an arbitrary linear equation in $\mathbb{Z}_{N}$: $$ ax = c\text{ in }\mathbb{Z}_{16} $$ Then the solution is $x = ca^{-1}$ in $\mathbb{Z}_{16}$ (Which follows from the definition of the inverse itself: $a^{-1}a\text{ in }\mathbb{Z}_{16}=1$). To compute an inverse of $a$ you can use Euler's theorem: $$ x^{\phi(N)}\text{ in }\mathbb{Z}_{N} = 1 $$ if $gcd(x,N) = 1$ (Note that $gcd(5,16)=1$) and where $\phi(N)$ is Euler's totient function, thus the inverse is: $$ x^{\phi(N)-1}\text{ in } \mathbb{Z}_{N} = x^{-1}\text{ in }\mathbb{Z}_{N} $$ Thus the solution becomes: $$ x = ca^{\phi(16)-1}\text{ in } \mathbb{Z}_{16} $$

Answer 3

First of all, we are able to divide any number by $\hat{5}$ in $\mathbb{Z}_{16}$ since $5$ is relatively prime to $16$.

Knowing this, the simplest way to discover the value of $x$ is to make a multiplication table showing only the multiples of $5 \pmod{16}$. Starting the table,

$5 \cdot 0 \equiv 0$
$5 \cdot 1 \equiv 5$
$5 \cdot 2 \equiv 10$
$5 \cdot 3 \equiv 15$
$5 \cdot 4 \equiv 4$
$\ldots$

You will discover that there is a unique value, $x$, for which $5x$ is congruent to $6 \pmod{16}$. This is your answer.