# understanding proof by contradiction

Below is not a completed proof but a logical structure i am unsure of. Given line 1, i do not understand line 2. I would understand it if it were:

The case when $$m=p_1n+r_1=p_2n+r_2$$ and $$r_1\ne r_2$$ and $$p_1=p_2$$ implies a contradiction that $$p_1\ne p_2$$ This case makes more sense to me because it includes $$p_1=p_2$$.

Can someone explain exactly how this should be done and if the proof below is correct could you explain line 2 to me and why line 3 works as well, sorry i am quite confused about this. It is the logic which i dont quite get.

i understand simple proof by contradiction but when there are not 'or' statements involved i find it quite confusing Thank you for your help.

What i want to prove

If, $$m=p_1n+r_1=p_2n+r_2$$ then $$p_1=p_2$$ and $$r_1=r_2$$ with $$0\le r_1,r_2\lt n$$

Start of proof (basic outline)

Assume $$m=p_1n+r_1=p_2n+r_2$$ and $$p_1\ne p_2$$ or $$r_1\ne r_2$$ with $$0\le r_1,r_2\lt n$$

The case when $$m=p_1n+r_1=p_2n+r_2$$ and $$r_1\ne r_2$$ implies a contradiction that $$p_1\ne p_2$$ as $$p_1n-p_2n$$ is not equal to 0.

This is equivalent to showing $$m=p_1n+r_1=p_2n+r_2$$ implies $$r_1 = r_2$$ is true

It follows that $$m=p_1n+r_1=p_2n+r_2$$ implies $$r_1 = r_2$$ and so $$p_1=p_2$$ must follow

Lets walk through this proof in a rather verbose way, and perhaps it will be more clear.

If we divide $$m$$ by $$n$$ into an integer and a remainder, we expect a unique result.

You learned that in about the 3rd grade. But, how do you prove it?

Suppose it is not true. Suppose there are two different results you might get.

Then one time you divide $$m$$ by $$n$$ and get $$p_1$$ with remainder $$r_1$$ and the other time you divide $$m$$ by $$n$$ you get $$p_2$$ and $$r_2.$$ In either case you should get.

$$np_1 + r_1 = np_2 + r_2 = m$$

Then if you subtracted one from the other.

$$np_1 + r_1 - np_2 - r_2 = 0$$

and factored

$$n(p_1 - p_2)+ (r_1 - r_2) = 0$$

If $$p_1, p_2$$ are distinct integers, $$|p_1 - p_2| \ge 1$$ and $$|n(p_1 - p_2)| > |n|$$

Which would imply that $$|r_1 - r_2| > n$$

But that is not possible if $$0

Nor is it possible that $$p_1 = p_2$$ yet $$r_1 \ne r_2$$

It is impossible to divide $$m$$ by $$n$$ and get different results.

Therefore the result when you divide $$m$$ by $$n$$ is unique.

• Thank you for your time, i think my reasoning is not really logically valid would you agree? for example line 2 of my 'proof' does not really imply a contradiction because i never assumed that $p_1=p_2$ – hitherematey Nov 13 '18 at 3:43