Find all incongruent solutions to $21x \equiv 14 \pmod{91}$.
I am able to work out the solution using Euclidean algorithm techniques, but the signs on the expression do not match up with the initial expression when I check my work. So by the linear congruence theorem, my solution has to satisfy: $$21x – 91y = 14$$ but after going through the process with the $\gcd(21, 91)$ my expression ends up as $$91 – 21(4) = 7$$ which I multiply by $2$ to get: $$91(2) – 21(8) = 14$$
Which would mean my solution has to have a negative somewhere in it. I can "put" a negative on one of my values and the original expression would be satisfied but that is not what I obtained through the work I did. Is the confusion in signs occurring on purpose or am I treating something wrong?
Best Answer
By definition, the congruence $$21x \equiv 14 \pmod{91} \tag{1}$$ is equivalent to the equation $$21x = 14 + 91t, t \in \mathbb{Z} \tag{2}$$
If we divide each term of equation 2 by $7$, we obtain the equivalent equation $$3x = 2 + 13t, t \in \mathbb{Z}$$ which is equivalent to the congruence $$3x \equiv 2 \pmod{13} \tag{3}$$
Hence, $$21x \equiv 14 \pmod{91} \Longleftrightarrow 3x \equiv 2 \pmod{13}$$
Since $\gcd(3, 13) = 1$, the congruence $3x \equiv 2 \pmod{13}$ has a solution. We can find it by applying the extended Euclidean algorithm. \begin{align*} 13 & = 4 \cdot 3 + 1\\ 3 & = 3 \cdot 1 \end{align*} Solving for $1$ in terms of $3$ and $13$ yields $$1 = 13 - 4 \cdot 3$$ Thus, $$1 \equiv -4 \cdot 3 \pmod{13} \implies -4 \equiv 3^{-1} \pmod{13}$$ Therefore, if we multiply both sides of congruence 3 by $-4$, we obtain $$x \equiv -8 \pmod{13}$$ To find all the solutions of congruence 1, we must find all the solutions of the inequality $$0 \leq -8 + 13t < 91$$ in the integers. \begin{align*} 0 & \leq -8 + 13t < 91\\ 8 & \leq 13t < 99\\ \end{align*} Hence, $1 \leq t \leq 7$. Therefore, the solutions of the congruence $21x \equiv 14 \pmod{91}$ are \begin{align*} x & \equiv 5 \pmod{91}\\ & \equiv 18 \pmod{91}\\ & \equiv 31 \pmod{91}\\ & \equiv 44 \pmod{91}\\ & \equiv 57 \pmod{91}\\ & \equiv 70 \pmod{91}\\ & \equiv 83 \pmod{91} \end{align*} which you can check by direct computation.