modular arithmetic - Solve the Following Congruences, or Explain Why They Have No Solution

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.

Answer

$1 = \ldots = 12 \cdot 28 - 5 \cdot 67$

Correct.

$\therefore x = 12$

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