I have the following problem:
Solve the following congruences, or explain why they have no solution:
(i) $28x \equiv 3 \pmod{67}$;
(ii) $29x \equiv 3 \pmod{67}$.
First, I was wondering why there would be a case where these would have no solution, and how we would know if these had no solution?
Lastly, my work is as follows, which I would appreciate if people could please take the time to verify:
i) If $x$ is an integer solution, then
$$28x = 3 + 67t$$
for some $t \in \mathbb{Z}$, or
$$28x – 67t = 3$$
Such pairs can be found using the Euclidean algorithm.
We first find the greatest common divisor of $28$ and $67$. To do this, we apply the Euclidean algorithm.
Since $67 > 28$, we divide $67$ by $28$: $67 = 2 \times 28 + 11$
Therefore, $GCD(67, 28) = GCD(28, 11)$.
$$28 = 2 \times 11 + 6$$
Therefore, $GCD(28, 11) = GCD(11, 6)$.
$$11 = 6 \times 1 + 5$$
Therefore, $GCD(11, 6) = GCD(6, 5)$.
$$6 = 1 \times 5 + 1 \ \ \ \text{(NOTE: The Extended Euclidean algorithm starts here.)}$$
Therefore, $GCD(6, 5) = GCD(5, 1)$.
$$5 = 1 \times 5 + 0$$
Therefore, $GCD(67, 28) = GCD(1, 0) = 1$.
We now apply the extended Euclidean algorithm.
The Euclidean algorithm recurses, starting at the step before the remainder was found to be $0$ (the last step that had a nonzero remainder).
$$1 = 6 – 1 \times 5$$
$$= 6 – 1 \times (11 – 6 \times 1) \ \ \ \text{(By substitution.)}$$
$$= 2 \times 6 – 1 \times 11 \ \ \ \text{(By algebra.)}$$
$$= 2(28 – 2 \times 11) – 1 \times 11$$
$$= 2 \times 28 – 5 \times 11$$
$$= 2 \times 28 – 5(67 – 2 \times 28)$$
$$= 12 \times 28 – 5 \times 67$$
$$\therefore x = 12$$
(ii) Applying the same procedure as above, I got $x = -30$.
I would greatly appreciate it if people could please take the time to clarify these questions and review my work.
EDIT: After doing research on my first question, I found out that the linear congruence $ax \equiv b \pmod{m}$ has no solutions if $GCD(a, m) \not\mid b$. But this still doesn't answer the question of why congruence equations sometimes have no solution, which was something that I was wondering.
Best Answer
Correct.
No, because $\,28 \cdot 12 - 3 = 333\,$ is not a multiple of $\,67\,$.
What you want is $\,28 x -67 t = 3 = 3 \cdot 1 = 3 \cdot (12 \cdot 28 - 5 \cdot 67) = (3 \cdot 12) \cdot 28 - (3 \cdot 5) \cdot 67\,$, so $\,x=3 \cdot 12 = 36\,$. And, of course, if $\,x\,$ is a solution then so is $\,x+67k\,$ for all $\,k\,$.