# Salvage of a given propostion

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.

• Could you provide your counterexample with $s < 0$? – Henry Swanson Dec 6 '13 at 2:08
• Hint: Using additional hypotheses will probably be easier. Changing the conclusion will probably change the $\mathop\bmod m$ into something else, I think. – dfeuer Dec 6 '13 at 2:10
• 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 – user113780 Dec 6 '13 at 3:03

## 1 Answer

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?

• 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 – user113780 Dec 6 '13 at 2:14
• That's true, but perhaps the way I've phrased it might make it clearer which other $a$ do not work. – Henry Swanson Dec 6 '13 at 2:16
• When all 3 (r,s,a) are negative there are several cases that cause the statement to be false. – user113780 Dec 6 '13 at 2:23
• @user113780, don't get distracted by signs. – dfeuer Dec 6 '13 at 2:27