1
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ What if $x=8{}$? $\endgroup$ Commented Mar 12, 2018 at 13:21
  • $\begingroup$ Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ Commented Mar 12, 2018 at 13:42
  • $\begingroup$ Your conclusion that $x\equiv3\pmod5$ is all that can be said. $\endgroup$
    – Lubin
    Commented Mar 12, 2018 at 13:44
  • $\begingroup$ Next time you see a question like this, try to produce a counterexample. You'd have learned a lot more doing it yourself. $\endgroup$ Commented Mar 12, 2018 at 13:58

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ No, it does not solve that, but it solves the original equation you asked for: $5x=15 \mod 25$ $\endgroup$ Commented Mar 12, 2018 at 13:50
  • $\begingroup$ Also, beware of your statement after "All I know is that". You cannot divide a modular equation by a non inversible element, and if you divide a modular equation by a number, the modulus does not change. For instance the following is ok: $5x=15\mod 25 \Rightarrow \frac{5}{2}x=\frac{15}{2}\mod 25$. $\endgroup$ Commented Mar 12, 2018 at 13:54
  • $\begingroup$ If you want to factorize in any way the modulus, you need the Chinese Remainder Theorem. $\endgroup$ Commented Mar 12, 2018 at 13:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .