Find $4x \equiv 7 \pmod{15}$ and $3x \equiv 5 \pmod{16}$ (different exercises)

Question

This is how I solved each:

$$4x \equiv 7\pmod {15} \\ 4x - 7 \equiv 0\pmod{15} \\ 4x-7 = 15k \Leftrightarrow 4x-15k= 7 \\ $$

$$15 = 4*3+3 \\ 4=3*1+1\\ 3=3*1+0$$

$$1 = 4-3*1 \\ 3 = 15-4*3 \\ 1 = 4 - (15-4*3)*1 \\ 1 = 4-15+4*3 \\ 1 = 4*4-15*1 \\ $$

$$7 = (7*4)*4-(7*1)*15$$

$7*4*4 = 112$ which is congruent with 7 in mod 15. Yet my book says the answer is 13. What went wrong?

The second one:

$$3x - 5 \equiv 0 \pmod{16} \\ 3x-5=16k\\ 3x-16k=5 \\$$

$$16=3*5+1\\ 3=1*3+0$$

$$1 = 16-3*5 \\ 5=16*5-3*5*5$$

Yet $3*5*5-5$ is not congruent with zero in mod 16. What went wrong?

Answer 1

Don't do that with such computations! For each of these congruence equations, you just have to find the modular inverse of the coefficient (which happens to be a modular unit since it is coprime to the modulus).

Example for the first congruence:

The modular inverse of $4\bmod 15$ is none other than itself since $4^2=16\equiv 1\mod 15$. So multiply both sides of the congruence equation by $4$: $$4x\equiv 7\mod 15\implies 4^2x\equiv \color{red}x\equiv 4\cdot 7=28\color{red}{\equiv 13\mod 15}.$$

Answer 2

You arrived at $7=28(4)-7(15)$, which means $7\equiv 4(28)-7(15)\equiv4(28)\equiv4(\boxed{13})$ (mod 15).

Similarly, $5=16(5)-3(25)$, means $5\equiv-3(25)\equiv-3(-7)\equiv3(\boxed{7})$ (mod 16).

You made a mistake in the second part because you forgot to take into account the negative sign.

Answer 3

To correctly pattern-match $\,\color{#c00}x\,$ in the above $\,\rm\color{#0a0}{scaled}\,$ Bezout equations do as follows.

$\qquad\ \begin{align} \ -7\cdot \color{#90f}{15}&\ +\ 4\cdot 7\cdot 4\,\ =\ \color{#0a0} 7\ \ [=\ \color{#0a0}{7\ {\rm times}} {\rm \ Bezout\ of\ } \gcd(15,4)=1\,]\\[.2em] \Rightarrow\ \bmod \color{#90f}{15}&\!:\,\ \ \ \ 4\cdot\color{#c00}{ 7\cdot 4} \ \equiv\ \ 7\\ \rm so &\,\ \ \ \ \ \ \ 4\ \cdot\ \color{#c00} x\ \ \, \equiv\, \ \ 7\ \ \ {\rm for}\ \ \ \color{#c00}{x\equiv 7\cdot 4}\equiv 13 \\[.6em] \ 5\cdot \color{#90f}{16}&\, + 3\cdot 5(-5)\, =\, \color{#0a0}5\ \ [=\ \color{#0a0}{5\ {\rm times}} {\rm \ Bezout\ of\ } \gcd(16,3)=1\,]\\[.2em] \Rightarrow\ \bmod \color{#90f}{16}&\!:\,\ \ 3\cdot\color{#c00}{ 5(-5)}\, \equiv\ 5\\ \rm so &\,\ \ \ \ \ 3\ \cdot\ \color{#c00} x\ \ \ \,\equiv\ \ \ \ 5\ \ \ {\rm for}\ \ \ \color{#c00}{x\equiv 5(-5)}\equiv 7 \end{align}$

Simpler $\bmod 15\!:\,\ 4x\equiv7\iff x \equiv \dfrac{7}{4}\equiv \dfrac{-8}4\equiv -2\equiv 13$

Similarly $\bmod 16\!:\,\ 3x\equiv 5\iff x\equiv \dfrac{5}3\equiv\dfrac{21}3\equiv 7\ $ where we subtracted or added the modulus to the numerator to make the division exact, a special case of Inverse Reciprocity.

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

Answer 4

With such small coefficients ($4$ and $3$), here is a quick and easy way to solve the congruences:

Mod $15$: $4x\equiv7\equiv22\equiv37\equiv\color{red}{52}=4\times13\implies x\equiv 13$

Mod $16$: $3x\equiv5\equiv\color{red}{21}=3\times7\implies x\equiv 7$