Consider the statement: For all integers $r$, $s$, and $a$, and natural numbers $m$, if $ra \equiv sa \pmod m$ then $r\equiv s \pmod m$.

I have found this statement to be false by the counterexample where $s$ is a negative number or $a$ is equal to zero.

the salvage wouldn't be a problem if I could change the quantifiers but the question specifically says:

If it is false, provide a counterexample and attempt to salvage the result. In other words, without changing the quantifiers (maintaining a universal statement) determine a different conclusion that makes the statement true or suggest additional hypotheses so that the conclusion follows.

I have messed around and tried to make the statement read if $ra \equiv sa \pmod m$ and $sa>0$ then $r\equiv s \pmod m$.

But I have found that it still fails, and at this point im really stumped and don't know of any conclustion or additional hypotheses I can make of that statement that would cause it to be true.

  • $\begingroup$ Could you provide your counterexample with $s < 0$? $\endgroup$ – Henry Swanson Dec 6 '13 at 2:08
  • $\begingroup$ Hint: Using additional hypotheses will probably be easier. Changing the conclusion will probably change the $\mathop\bmod m$ into something else, I think. $\endgroup$ – dfeuer Dec 6 '13 at 2:10
  • $\begingroup$ couter example were s < 0: a=-3 r = -2 s= -8---> -3*-2 ≡ -3 *-8 (mod 9) ---> 6≡6________________ r≡s(mod m) ----> -2≡-8(mod 9)---> -2≢1 $\endgroup$ – user113780 Dec 6 '13 at 3:03

Hint: if $ra \equiv sa \pmod m$, then $(ra - sa) \mid m$. You were asked to show the (false) statement: $$(ra - sa) \mid m \implies (r - s) \mid m$$ Why can you not get there when $a = 0$? Are there other problematic $a$? What hypothesis excludes these $a$?

EDIT: Note that $(ra - sa) \mid m$ means that $a(r-s) \mid m$. Let $b = r - s$, and the problem is: when is this true: $$ab \mid m \implies b \mid m$$ For $a = 0$, it doesn't work. What other $a$s is this false for?

  • $\begingroup$ if I have where a = 0 then r(0)≡ s(0)(mod m) ===> 0 ≡ 0 but when I remove the a for the second part of the statement a≡s(mod m) will not be true in a lot of cases $\endgroup$ – user113780 Dec 6 '13 at 2:14
  • $\begingroup$ That's true, but perhaps the way I've phrased it might make it clearer which other $a$ do not work. $\endgroup$ – Henry Swanson Dec 6 '13 at 2:16
  • $\begingroup$ When all 3 (r,s,a) are negative there are several cases that cause the statement to be false. $\endgroup$ – user113780 Dec 6 '13 at 2:23
  • 1
    $\begingroup$ @user113780, don't get distracted by signs. $\endgroup$ – dfeuer Dec 6 '13 at 2:27

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.