3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Barry Smith Feb 3 '16 at 2:56
  • $\begingroup$ but I didn't get $(-2)$ as my other solution, i got $2$ so how am I able to switch that to a $(-2)$? $\endgroup$ – dc3rd Feb 3 '16 at 3:01
  • $\begingroup$ 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 $\endgroup$ – Barry Smith Feb 3 '16 at 3:46
  • $\begingroup$ 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? $\endgroup$ – dc3rd Feb 3 '16 at 3:56
  • 1
    $\begingroup$ 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$$ $\endgroup$ – Paul Sinclair Feb 3 '16 at 5:00
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.