Solve ## 6x\equiv 15\pmod {21} ##.

[Math100]

Homework Statement

Solve the following linear congruence:
$6x\equiv 15\pmod {21}$.

Relevant Equations

None.

Consider the linear congruence $6x\equiv 15\pmod {21}$.
Applying the Euclidean Division yields:
$21=3\cdot 6+3$
$6=2\cdot 3+0$.
Then $gcd(6, 21)=3$.
Since $3\mid 15$, it follows that the linear congruence $6x\equiv 15\pmod {21}$ has
a unique solution modulo $n$.
Observe that $x\equiv (6+\frac{21}{3}t)\pmod {21}$ where $0\leq t\leq 2$.
Thus $x\equiv (6+7t)\pmod {21}$.
Therefore, $x\equiv 6\pmod {21}, x\equiv 13\pmod {21}$ and $x\equiv 20\pmod {21}$.

 

[fresh_42]

Homework Statement:: Solve the following linear congruence:
$6x\equiv 15\pmod {21}$.
Relevant Equations:: None.

Consider the linear congruence $6x\equiv 15\pmod {21}$.
Applying the Euclidean Division yields:
$21=3\cdot 6+3$
$6=2\cdot 3+0$.
Then $gcd(6, 21)=3$.
Since $3\mid 15$, it follows that the linear congruence $6x\equiv 15\pmod {21}$ has
a unique solution modulo $n$.

You found three solutions, so how can they be unique?

Observe that $x\equiv (6+\frac{21}{3}t)\pmod {21}$ where $0\leq t\leq 2$.

It seems to be right since you have found the correct solutions, but why is this the case?

We have
\begin{align*}
6x\equiv 15 \pmod{21}&\Longrightarrow 21\,|\,(6x-15)=3\cdot (2x-5)\\
&\Longrightarrow 7\,|\,2x-5\\
&\Longrightarrow x=(7s+5)/2 \wedge 0\leq x \leq 20\\
&\Longrightarrow s\in \{1,3,5\}\\
&\Longrightarrow x\in\{6,13,20\}
\end{align*}

How did you get $x\equiv (6+7t)\pmod {21}$ where $0\leq t\leq 2$?

Thus $x\equiv (6+7t)\pmod {21}$.
Therefore, $x\equiv 6\pmod {21}, x\equiv 13\pmod {21}$ and $x\equiv 20\pmod {21}$.

 

[Math100]

You found three solutions, so how can they be unique?

It seems to be right since you have found the correct solutions, but why is this the case?

We have
\begin{align*}
6x\equiv 15 \pmod{21}&\Longrightarrow 21\,|\,(6x-15)=3\cdot (2x-5)\\
&\Longrightarrow 7\,|\,2x-5\\
&\Longrightarrow x=(7s+5)/2 \wedge 0\leq x \leq 20\\
&\Longrightarrow s\in \{1,3,5\}\\
&\Longrightarrow x\in\{6,13,20\}
\end{align*}

How did you get $x\equiv (6+7t)\pmod {21}$ where $0\leq t\leq 2$?

$x\equiv (x_{0}+\frac{n}{d}t)\pmod {n}$
$x\equiv (6+\frac{21}{3}t)\pmod {21}$

 

[Math100]

As for $0\leq t\leq 2$, I got this because $gcd(6, 21)=3$, so $t$ must be $0\leq t\leq 2$ or $0\leq t<3$.

 

[Math100]

Since you claimed that three solutions aren't unique, then is the answer just $x\equiv 6\pmod {21}$?

 

[fresh_42]

Since you claimed that three solutions aren't unique, then is the answer just $x\equiv 6\pmod {21}$?

No, all three are possible solutions.

You only get unique solutions if the greatest common divisor is $1.$ Here we have $3$. The reason is that $\operatorname{gcd}(a,b)$ can be written as
$$
\operatorname{gcd}(a,b)=s\cdot a+t\cdot b
$$
If we had $\operatorname{gcd}(a,b)=1,$ then $1\equiv s\cdot a \pmod b$ and $a$ can be inverted: $s\equiv 1/a \pmod b.$ Now we could solve all equations $a\cdot x \equiv c \pmod b$ simply by multiplying it with $s$. Hence
$$
s\cdot (a\cdot x) \equiv (s\cdot a)\cdot x \equiv 1\cdot x \equiv x\equiv s\cdot c \pmod b.
$$

But here we have only the equation $3=1\cdot 21 - 3\cdot 6$ and $6$ cannot be inverted modulo $21.$

 

[Math100]

But which method is correct? The one you showed me above with $x=(7s+5)/2\land 0\leq x\leq 20\implies s\in {1, 3, 5}\implies x\in {6, 13, 20}$, or the one I used?

 

[fresh_42]

But which method is correct? The one you showed me above with $x=(7s+5)/2\land 0\leq x\leq 20\implies s\in {1, 3, 5}\implies x\in {6, 13, 20}$, or the one I used?

Both are ok. Your only mistake was to call the solution unique. We have three valid solutions so they cannot be unique.