# Opinion on proof(Integer divisibility)

• Jan 29th 2010, 01:04 PM
gate13
Opinion on proof(Integer divisibility)
Good day to all. I have been asked to prove the following proposition:

Let m and n be integers. Use the contradiction method to prove that the quotient and the remainder of the division of m by n are unique.

The following is a rough proof I have come up with. I was wondering if someone could offer their opinion on my proof, if I have made glaring mistakes and such. Any input would be greatly appreciated. I have omitted the theorems used, to avoid making the post heavier than it already is.

Proof:

We assume that the quotient and remainder are not unique. Then

m = q1n + r1 and m = q2n + r2

m=m

q1n + r1=q2n + r2

n(q1-q2) = -(r1-r2)

This implies the equality 0 = 0 since zero is the only number equal to its negative.

Therefore n(q1-q2) = 0 => n = 0 or (q1-q2) = 0

if n = 0 => r1 = r2 and we have q1 = ((n-r1)/n) and q2 = ((n-r1)/n) i.e. q1 = q2

if (q1-q2) = 0 => q1 = q2 and -(r1-r2) = 0 => r1 = r2
Q.E.D.
• Jan 29th 2010, 02:28 PM
Bruno J.
Good day!

This part :

Quote:

Originally Posted by gate13
n(q1-q2) = -(r1-r2)

This implies the equality 0 = 0 since zero is the only number equal to its negative.

is wrong. Both sides are indeed zero but the reason you give is not correct. What you're saying is equivalent to " $x=-y$ implies $x=y=0$" which is obviously wrong. There is another reason why both sides are $0$; consider the fact that the left side is a multiple of $n$, but that the right side is less than $n$ in absolute value...
• Jan 29th 2010, 02:33 PM
tonio
Quote:

Originally Posted by gate13
Good day to all. I have been asked to prove the following proposition:

Let m and n be integers. Use the contradiction method to prove that the quotient and the remainder of the division of m by n are unique.

The following is a rough proof I have come up with. I was wondering if someone could offer their opinion on my proof, if I have made glaring mistakes and such. Any input would be greatly appreciated. I have omitted the theorems used, to avoid making the post heavier than it already is.

Proof:

We assume that the quotient and remainder are not unique. Then

m = q1n + r1 and m = q2n + r2

m=m

q1n + r1=q2n + r2

n(q1-q2) = -(r1-r2)

This implies the equality 0 = 0 since zero is the only number equal to its negative.

And what has this fact to do with what you got above?? You didn't get something like $x=-x$ , you got $n(q_1-q_2)=-(r_1-r_2)$ and thus you cannot deduce from this that $n(q_1-q_2)=0$ . I'd try using $r_i=0\,\,\,or\,\,\,|r_i| .

Tonio

Therefore n(q1-q2) = 0 => n = 0 or (q1-q2) = 0

if n = 0 => r1 = r2 and we have q1 = ((n-r1)/n) and q2 = ((n-r1)/n) i.e. q1 = q2

if (q1-q2) = 0 => q1 = q2 and -(r1-r2) = 0 => r1 = r2
Q.E.D.

.
• Jan 29th 2010, 02:50 PM
Bruno J.
How is $|r_i| true? You mean $|r_i|, as I wrote.
• Jan 29th 2010, 07:00 PM
gate13
Thanks Bruno J. and tonio for your input. As I began thinking about the proof I realized that my deductions from n(q1-q2) = -(r1-r2) were questionable at best. They were obviously wrong. I am going to rework the exercise immediately but I have an idea of where the proof should lead. Should I have any questions, I will post my problem. Again thanks for your inputs.
• Jan 29th 2010, 10:35 PM
tonio
Quote:

Originally Posted by Bruno J.
How is $|r_i| true? You mean $|r_i|, as I wrote.

Of course, in both cases: n divides m with remainder.

Tonio