# 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?

• Just rewrite the final equation as $21 (-8) - 91 (-2) = 14$. It has the form you gave for the linear congruence theorem, and from it you see that $x=-8$ is a solution. It only remains to see that all other solutions are congruent to -8 modulo 13, so that, for instance, 5 is another solution. – Barry Smith Feb 3 '16 at 2:56
• but I didn't get $(-2)$ as my other solution, i got $2$ so how am I able to switch that to a $(-2)$? – dc3rd Feb 3 '16 at 3:01
• In your formula, 2 is the number multiplying 91. But in the linear congruence theorem above, the solution x is supposed to be the number multiplying 21. That number is -8, which is a solution – Barry Smith Feb 3 '16 at 3:46
• But wouldn't the fact that I got a positive 2 for the solution to y and applying both solutions i. e. $x = (-8)$ and $y= 2$ to the expression from the linear congruence theorem to check if the solution i obtained actually satisfies it and after doing so I see that those specific values: $x = (-8)$, $y= 2$ do not satisfy the expression. Doesn't that mean that my solution is invalid? – dc3rd Feb 3 '16 at 3:56
• Barry's solution is your solution, just rewritten in a form that fits the original congruence: $$91(2) - 21(8) = 14$$ $$(-21(8)) - (-91(2)) = 14$$ $$21(-8) - 91(-2) = 14$$. Now you have it in the form you gave from the lineare congruence theorem. Personally, I would rewrite it further as $$21(-8) - 14 = 91(-2)$$, as this is the definition of $$21(-8) \equiv 14 \mod 91$$ – Paul Sinclair Feb 3 '16 at 5:00

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.

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

$$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.