Results 1 to 6 of 6

Math Help - Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n divid

  1. #1
    Newbie
    Joined
    May 2011
    From
    Florida
    Posts
    16

    Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n divid

    Given 0<n<m, show that there exists some t, n≤t<m, so that m-n divides t.

    Please help! Thanks!
    I started by assuming t does not divide m-n
    Then
    t = (m-n)q + r , 0<r<(m-n)
    t = mq - nq + r

    I don't really know where to go from there.
    Last edited by scruz10; July 4th 2011 at 09:21 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d

    Quote Originally Posted by scruz10 View Post
    Given 0<n<m, show that there exists some t, n≤t<m, so that m-n divides t.

    Please help! Thanks!
    I started by assuming t does not divide m-n
    Then
    t = (m-n)q + r , 0<r<(m-n)
    t = mq - nq + r

    I don't really know where to go from there.
    The Pigeonhole Principle!

    There are m-n possible choices of t, so...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    From
    Florida
    Posts
    16

    Re: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d

    Ok This kind of helps. I put There are m-n integers between m,n. Call this set of integers S. Let m-n = k
    0 < n < m => 0 < k < m
    S = {n, n+1, n+2....n+(k-1)}, t is an element of S
    Let t = n and Let k=n
    Then m - n = n
    n divides n => t divides n => t divided (m-n)

    Does that seem correct?
    Last edited by scruz10; July 4th 2011 at 11:57 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d

    Quote Originally Posted by scruz10 View Post
    Let t = n and Let k=n
    Then m - n = n
    n divides n => t divides n => t divided (m-n)

    Does that seem correct?
    You have only considered the case when k = n, i.e., m = 2n.

    Let's denote the remainder when x is divided by y as x mod y. Note that either (t + 1) mod (m - n) = (t mod (m - n)) + 1 or (t + 1) mod (m - n) = 0. In words, when t increases by 1, the remainder when divided by m - n either increases by 1 or goes to 0.

    If n mod (m - n) = 0, we are done. The "worst" case would be if n mod (m - n) = 1. Then (n + 1) mod (m - n) = 2, (n + 2) mod (m - n) = 3, etc. How long can this go on before we get to (n + i) mod (m - n) = 0 for some i?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2011
    From
    Florida
    Posts
    16

    Re: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d

    Thanks! Should that be t mod (m-n) = 1 in the 2nd part, and (t + 1) mod (m-n) = 2, etc.?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d

    Should that be t mod (m-n) = 1 in the 2nd part, and (t + 1) mod (m-n) = 2, etc.?
    The goal is to prove that t exists. We have not found it yet until the end of the proof. So in my hint I did mean starting with finding n mod (m - n). If it is 0, then t = n; if it is 1, then t = m - 1; if it is some other number between 2 and m - n - 1, then t is between n + 1 and m - 2. In fact, it is not hard to see that t = m - k where k can be easily found from n mod (m - n) (provided the last remainder is nonzero).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. show that f'(c) exists
    Posted in the Differential Geometry Forum
    Replies: 7
    Last Post: October 7th 2011, 08:53 AM
  2. Replies: 2
    Last Post: March 19th 2011, 01:38 AM
  3. Replies: 3
    Last Post: July 27th 2010, 03:46 PM
  4. Need to show {x | f(x) ≤ g(x)} closed if f,g continuous.
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 15th 2009, 02:27 AM
  5. Replies: 1
    Last Post: May 27th 2008, 07:56 AM

Search Tags


/mathhelpforum @mathhelpforum