Prove a mod b = b mod a iff a=b

Question

I'm just starting to learn the three types of proofs and I came across this question.

                 a mod b = b mod a iff a=b

I tried looking for solution to prove this but couldn't find it. Most examples I have are of the same divisor like: a mod n = b mod n. But i couldn't find anything on this.

I assumed it would be by using a contradiction proof but what got me confused is the if and only if condition.

Thanks for any help you send this way!!

Well you have both $a$ divides $b$ and $b$ divides $a$ so..... — fleablood, Aug 30 '19 at 23:22
It seems you are using "mod" to mean remainder rather than as a equivalence clasee — Henry, Aug 30 '19 at 23:44

score 5 · Accepted Answer · answered Aug 30 '19 at 23:19

5

Suppose $a\neq b$. Then, without loss of generality we can assume that $a>b$. In that case $b\pmod a$ is $b$. But $a\pmod b$ is the remainder of $a$ on division by $b$, hence it is less than $b$.

answered Aug 30 '19 at 23:19

lulu

70,402

@RJ563 this is an incomplete proof. You have to prove it in both directions (since this is an "iff" proof. See my solution, which is superior to this (and is a complete proof). – piznajko Jan 12 '21 at 18:42
1

@piznajko Yes, apparently I felt that "$a=b\implies (a\pmod b)=(b\pmod a)$" was too obvious to require any mention. Still feel that way, as it happens. – lulu Jan 12 '21 at 18:47

score 0 · Answer 2 · answered Aug 30 '19 at 23:22

When you have a statement with an equivalence (an "if and only if") you have to prove two things. If you have

A iff B

You must prove $A \implies B$ and $B \implies A$. When proving those two things you can then use a proof by contradiction. For each of the things, separately. Or you can mix in two types of proofs, one for each implication.

score 0 · Answer 3 · answered Jan 12 '21 at 18:37

Since this is an if and only if proof, we have to do it in two directions. As is often the case in if and only if proofs, one direction is much easier to do than the other. We will do the easy direction first.

Proof.

⇐ We assume a=b and prove a mod b = b mod a. But this is clearly true, since x mod x= 0 for all x, and a and b are equal.

⇒ Here we have to prove that if a mod b = b mod a, then a=b. Try to find a direct proof, and then give up and do the contrapositive: assume a ≠ b, and prove that a mod b ≠ b mod a. There are two possible cases: a < b and b < a (we’ve already assumed a≠b).

Case 1: a < b Then a mod b=a. But b mod a, as we noted, is strictly less than a, so it cannot be equal to a and hence can’t be equal to a mod b.

Case 2: a > b Then b < a, and the proof is the same as above with a replaced by b and b replaced by a.

□

Source

Prove a mod b = b mod a iff a=b

3 Answers3