# Thread: Opinion on proof(Integer divisibility)

1. ## 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.

2. Good day!

This part :

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 "$\displaystyle x=-y$ implies $\displaystyle x=y=0$" which is obviously wrong. There is another reason why both sides are $\displaystyle 0$; consider the fact that the left side is a multiple of $\displaystyle n$, but that the right side is less than $\displaystyle n$ in absolute value...

3. 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 $\displaystyle x=-x$ , you got $\displaystyle n(q_1-q_2)=-(r_1-r_2)$ and thus you cannot deduce from this that $\displaystyle n(q_1-q_2)=0$ . I'd try using $\displaystyle r_i=0\,\,\,or\,\,\,|r_i|<q_i\,,\,\,i=1,2$ .

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.

.

4. How is $\displaystyle |r_i|<q_i$ true? You mean $\displaystyle |r_i|<n$, as I wrote.

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

6. Originally Posted by Bruno J.
How is $\displaystyle |r_i|<q_i$ true? You mean $\displaystyle |r_i|<n$, as I wrote.

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

Tonio