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
    $\begingroup$ What if $x=8{}$? $\endgroup$ – Lord Shark the Unknown Mar 12 '18 at 13:21
  • $\begingroup$ Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Mar 12 '18 at 13:42
  • $\begingroup$ Your conclusion that $x\equiv3\pmod5$ is all that can be said. $\endgroup$ – Lubin Mar 12 '18 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$ – John Brevik Mar 12 '18 at 13:58
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$
  • $\begingroup$ No, it does not solve that, but it solves the original equation you asked for: $5x=15 \mod 25$ $\endgroup$ – Tal-Botvinnik Mar 12 '18 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$ – Tal-Botvinnik Mar 12 '18 at 13:54
  • $\begingroup$ If you want to factorize in any way the modulus, you need the Chinese Remainder Theorem. $\endgroup$ – Tal-Botvinnik Mar 12 '18 at 13:54
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$

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.