Solving the congruence $7x \equiv 41 \mod{13}$

Question

I have to solve the following linear congruence:

$$7x \equiv 41 \mod{13}$$

The question where I got this from comes in two parts. The first is that it asks to find the set of the inverses of $7 \mod 13$, which turns out to be $[2]_{13}$ but, I found that solution by solving the linear diophantine equation $$7x - 13k - 41$$ which is just the original equation in disguise i.e. $7x \equiv 41 \mod{13}$.

Now, I'm terribly confused as to the solution of the congruence equation. Where am I going wrong and how should I proceed?

Thanks!

EDIT: From @Bill's hint

\begin{align} 7x &\equiv 41 \mod{13} \\ x &\equiv \frac{41}{7} \mod{13} \\ x &\equiv \frac{28}{7} \mod{13} \quad (?) \\ x &\equiv 4 \mod{13} \\ \end{align}

Then, this gives me the solution $[4]_{13}$.

Answer 1

Reduce the congruence to $7x \equiv 2$. Since $\gcd(7,13) = 1$, there exists a unique inverse of $7$ modulo $13$. Note that the inverse is just $2$ since $7 \cdot 2 \equiv 1 \pmod {13}$. Then it follows that $(7)(7^{-1})x \equiv x \equiv 2(7^{-1}) \equiv 4 \pmod {13}$ and that is the solution set.

Answer 2

Hint $\ {\rm mod}\ 13\!:\ \dfrac{41}7 \equiv \dfrac{28}7 = 4\ \ $ by $\ \ 41\equiv 41\!-\!13 = 28$

Alternatively $\ \dfrac{41}{7}\equiv\dfrac{(-2)(-1)}{-6}\equiv \dfrac{-2}{-2}\dfrac{12}3\equiv 4\ \ $ by $\ \ \begin{eqnarray}41&&\equiv\ \ 2\\ 7 &&\equiv -6\end{eqnarray}$

Alternatively $\ \dfrac{41}{7}\equiv \dfrac{2}7\equiv \dfrac{4}{14}\equiv \dfrac{4}1\ $ by Gauss's Algorithm.

Such twiddling (adding/subtracting the modulus from numerator or denominator till things divide or factor nicely) works quite well for small numbers (more generally we can use Inverse Reciprocity to make the quotient exact. For larger numbers one can invert the denominator by the Extended Euclidean Algorithm, or Gauss's algorithm if the modulus is prime.

Beware $\ $ The use of fractions in modular arithmetic is valid only when the denominator is invertible, i.e. coprime to the modulus. Otherwise the quotient need not be unique, for example mod $\rm\:10,\:$ $\rm\:4\,x\equiv 2\:$ has solutions $\rm\:x\equiv 3,8,\:$ so the "fraction" $\rm\:x \equiv 2/4\pmod{10}\,$ cannot designate a unique solution of $\,4x\equiv 2.\,$ Indeed, the solution is $\rm\:x\equiv 1/2\equiv 3\pmod 5,\,$ which requires canceling $\,2\,$ from the modulus too, since $\rm\:10\:|\:4x-2\iff5\:|\:2x-1.\:$

Generally the grade-school rules of fraction arithmetic apply universally (i.e. in all rings) where the denominators are invertible. This fundamental property will be clarified conceptually when one learns in university algebra about the universal properties of fractions rings and localizations.

Answer 3

$$\tag{1} 7 x - 13k = 41$$

Let $a = x - 2k$, so $$\tag{2}x = a + 2k$$.

Substituting $(2)$ into $(1)$: $$7(a + 2k) - 13k = 41$$ $$7a + k = 41$$ $$k = 41 - 7a \tag{3}$$

Substituting $(3)$ into $(2)$: $$x = a + 2(41 - 7a)$$ $$x = 82 - 13a$$ Plug any integer you like into $a$, and out pops a valid $x$.