Find all incongruent solutions to $21x \equiv 14 \pmod{91}$ 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? 
 A: 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.
A: Simpler method to execute the problem is to first simplify it using gcd of $(21, 14, 91)$ as divisor (gcd=7). The equation becomes $3x≡2 (mod 13)$. Use values 0 through 12 to find solution. Extended Euclidean Algorithm will be useful when divisor and dividend are large numbers. The equation gets solution when $f(x) = f(5): (5*3)-2 = 13$; $13|13$. Now take all multiples of 13 adding each time 5; to get $5, 18, 31, 44, 57, 70$ and $83$ as illustrated above (till value less than main divisor i.e. 91). These all provide required solutions to the equation by substituting these values to x: $21x≡14 (mod 91)$
Prof. Dr. Shabir Ahmad Mir
A: $$21x\equiv 14\pmod{91}\stackrel{:7}\iff 3x\equiv 2\equiv 15\pmod{13}$$
$$\stackrel{:3}\iff x\equiv 5\pmod{13}$$
All integers of the form $13k+5$ for some $k\in\mathbb Z$ are the solutions.
