1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ has no solutions if gcd(a,m) ∤ b If $ax - mt = b$ and $d = \gcd(a,m) \mid a$ and $d \mid m$, then $d \mid b$. If it doesn't, there are no solutions. $\endgroup$ – dxiv Aug 26 '18 at 7:16
  • $\begingroup$ @dxiv Ok, thanks for the clarification. $\endgroup$ – The Pointer Aug 26 '18 at 7:17
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ahh, thanks for that. So we have to multiply the entire thing by 3 so that we get it equal to 3 instead of 1, which is what we were seeking? $\endgroup$ – The Pointer Aug 26 '18 at 2:42
  • $\begingroup$ Also, can you please address the first question? I’m confused about that. $\endgroup$ – The Pointer Aug 26 '18 at 2:42
  • 1
    $\begingroup$ @ThePointer Yes, never forget the ultimate goal ahead. $\,28x-67t=3\,$ has solutions only because $3$ is a multiple of $\gcd(28,67)=1$. So the first step was to get the $\gcd$ in the required form $28a+67b=1$, but then there still remains a factor of $3$ to apply. P.S. I believe this addresses your first question as well. $\endgroup$ – dxiv Aug 26 '18 at 2:44

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.