Results 1 to 6 of 6

Math Help - Opinion on proof(Integer divisibility)

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    34

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Good day!

    This part :

    Quote Originally Posted by gate13 View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by gate13 View Post
    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|<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.

    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    How is |r_i|<q_i true? You mean |r_i|<n, as I wrote.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    34
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Bruno J. View Post
    How is |r_i|<q_i true? You mean |r_i|<n, as I wrote.

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

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: March 7th 2010, 02:41 PM
  2. Opinion on proof!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2010, 05:43 AM
  3. Divisibility proof in random integer subset
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 10th 2009, 11:14 AM
  4. Divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 10th 2008, 07:07 AM
  5. divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2007, 10:39 AM

Search Tags


/mathhelpforum @mathhelpforum