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

Printable View

• Jul 4th 2011, 09:04 AM
scruz10
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.
• Jul 4th 2011, 09:42 AM
Swlabr
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
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...
• Jul 4th 2011, 10:10 AM
scruz10
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?
• Jul 4th 2011, 01:04 PM
emakarov
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
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?
• Jul 5th 2011, 04:36 PM
scruz10
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.?
• Jul 6th 2011, 06:08 AM
emakarov
Re: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d
Quote:

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