If $5x \equiv 15 \pmod{25}$, then definitely $x \equiv 3 \pmod{25}$. Is this true or false?

336 Views Asked by At

I don't understand how to prove this statement true or false.

If $5x \equiv 15 \pmod{25}$, then definitely $x \equiv 3 \pmod{25}$.

All I know is that $\frac{5}5x \equiv \frac{15}5 \pmod{\frac{25}5}$ = $x \equiv 3 \pmod{5}$, and $x \cdot 5 \equiv 3 \cdot 5 \pmod{25}$ = $5x \equiv 15 \pmod{25}$, how do you prove this equation?

3

There are 3 best solutions below

3
On BEST ANSWER

The statement is false, because 5 is not divisible in $\mathbb Z_{25}$. And that is because gcd$(5,25)\neq 1$.

Simply put, you want to divide your equation by 5, to isolate $x$. Well dividing by 5 is to multiply by the inverse of 5, i.e. the number $b$ such that $5\cdot b=1\mod 25$. Note that there are no solutions for $b$, since the integer $5b$ ends either with 0 or 5, thus making it impossible to be congruent to 1 mod 25.

That means that you cannot divide by 5. All you have left is to try out the 25 possible values for $x$ in your equation. $x=3$ definitely solves it, but also does $x=8$, and probably more numbers.

In conclusion, your equation has multiple solutions, so no, $x$ is not definitely 3.

0
On

The congruence $5x \equiv 15 \pmod{25}$ means that there exists $t \in \mathbb{Z}$ such that $$5x = 15 + 25t$$ Dividing each side of the equation by $5$ yields $$x = 3 + 5t$$ Therefore, if $$x \equiv 3 \pmod{5}$$ it satisfies the congruence $5x \equiv 15 \pmod{25}$. There are five such equivalence classes modulo $25$. They are \begin{align*} x & \equiv 3 \pmod{25}\\ x & \equiv 8 \pmod{25}\\ x & \equiv 13 \pmod{25}\\ x & \equiv 18 \pmod{25}\\ x & \equiv 23 \pmod{25} \end{align*} Hence, the statement is false.

0
On

When in doubt, do something.

There are theorems and postulates to show this is false but if you aren't sure what to do... just work.

$5x \equiv 15\mod 25 \implies$

$5x= 15 + 25k$ for some $k$ which implies

$x = 3 + 5k$ which... is not the same thing as $x \equiv 3 \mod 25$.

Counter examples are $x$ are $8, 13,18,23$.

It does seem that that if $mx \equiv mj \mod n$ and $m|n$ then $x \equiv j\mod \frac nm$ and that $x \equiv j + \frac nm*k \mod n$ for some $k$.

What do you think happens if $m\not \mid n$? Or if $\gcd(m,n) =d$? Or if $\gcd(m,n) = 1$?