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.

Printable View

- July 4th 2011, 09:04 AMscruz10Help 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. - July 4th 2011, 09:42 AMSwlabrRe: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d
- July 4th 2011, 10:10 AMscruz10Re: 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? - July 4th 2011, 01:04 PMemakarovRe: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n d
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? - July 5th 2011, 04:36 PMscruz10Re: 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.?

- July 6th 2011, 06:08 AMemakarovRe: Help with proof, Given 0<n<m, show that there exists some t, n≤t<m, so that m-n dQuote:

Should that be t mod (m-n) = 1 in the 2nd part, and (t + 1) mod (m-n) = 2, etc.?