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

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

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.

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

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

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

3. ## 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?

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

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?

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

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