4
$\begingroup$

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!!

$\endgroup$
2
  • $\begingroup$ Well you have both $a$ divides $b$ and $b$ divides $a$ so..... $\endgroup$
    – fleablood
    Aug 30, 2019 at 23:22
  • 1
    $\begingroup$ It seems you are using "mod" to mean remainder rather than as a equivalence clasee $\endgroup$
    – Henry
    Aug 30, 2019 at 23:44

3 Answers 3

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @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). $\endgroup$
    – piznajko
    Jan 12, 2021 at 18:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – lulu
    Jan 12, 2021 at 18:47
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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