# Question with the Chinese Remainder Theorem

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

Let and let be its image under the map for each prime . Suppose that for each .

Let .

I want to show that . The hint given is to apply the Chinese Remainder Theorem to the first primes then take .

I've managed to get that where is the product of the first primes using CRT but not sure about anything more. Bounding seemed like the way to go but doesn't seem easy.

Let .

I want to show that . The hint given is to apply the Chinese Remainder Theorem to the first primes then take .

I've managed to get that where is the product of the first primes using CRT but not sure about anything more. Bounding seemed like the way to go but doesn't seem easy.

Last edited by _gcx; 1 week ago

0

reply

Report

#2

It seems that it wouldn't be significantly harder to show for any integer j (basically "shifting" the window you're intersecting with S).

That should then be enough to "bridge" intermediate values between m_k and m_{k+1} I think. (You can do jumps of m_k until m_{k+1} directly, and values in-between can't be different enough to break convergence to 0).

May be something more elegant, but I think that works.

That should then be enough to "bridge" intermediate values between m_k and m_{k+1} I think. (You can do jumps of m_k until m_{k+1} directly, and values in-between can't be different enough to break convergence to 0).

May be something more elegant, but I think that works.

0

reply

(Original post by

It seems that it wouldn't be significantly harder to show for any integer j (basically "shifting" the window you're intersecting with S).

That should then be enough to "bridge" intermediate values between m_k and m_{k+1} I think. (You can do jumps of m_k until m_{k+1} directly, and values in-between can't be different enough to break convergence to 0).

May be something more elegant, but I think that works.

**DFranklin**)It seems that it wouldn't be significantly harder to show for any integer j (basically "shifting" the window you're intersecting with S).

That should then be enough to "bridge" intermediate values between m_k and m_{k+1} I think. (You can do jumps of m_k until m_{k+1} directly, and values in-between can't be different enough to break convergence to 0).

May be something more elegant, but I think that works.

Is the general idea that #S[N]/N = #S[j + m_k]/(j + m_k) for some k, j, then the RHS vanishes as k -> infinity?

0

reply

Report

#4

(Original post by

Cheers, it seems this end of the question is oddly inelegant compared to the previous part.

Is the general idea that #S[N]/N = #S[j + m_k]/(j + m_k) for some k, j, then the RHS vanishes as k -> infinity?

**_gcx**)Cheers, it seems this end of the question is oddly inelegant compared to the previous part.

Is the general idea that #S[N]/N = #S[j + m_k]/(j + m_k) for some k, j, then the RHS vanishes as k -> infinity?

Now what if N>m_k *isn't* a multiple of m_k. Then we have a "partial block" of size N mod m_k at the end. But that block can't contribute more than a full block,so adds at most m_k/2^k to the total. And since N >m_k the contribution of the partial block divided by N must tend to 0 and can't mess things up.

1

reply

(Original post by

So how I'm thinking about it is that we know that for any block [j,j+m_k) we'll have at most m_k / 2^k (I think will be the bound you have but the exact details don't matter) members of S. In particular, we can take blocks in steps of m_k to show #S[N] <=N/2^k when N is a multiple of m_k.

Now what if N>m_k *isn't* a multiple of m_k. Then we have a "partial block" of size N mod m_k at the end. But that block can't contribute more than a full block,so adds at most m_k/2^k to the total. And since N >m_k the contribution of the partial block divided by N must tend to 0 and can't mess things up.

**DFranklin**)So how I'm thinking about it is that we know that for any block [j,j+m_k) we'll have at most m_k / 2^k (I think will be the bound you have but the exact details don't matter) members of S. In particular, we can take blocks in steps of m_k to show #S[N] <=N/2^k when N is a multiple of m_k.

Now what if N>m_k *isn't* a multiple of m_k. Then we have a "partial block" of size N mod m_k at the end. But that block can't contribute more than a full block,so adds at most m_k/2^k to the total. And since N >m_k the contribution of the partial block divided by N must tend to 0 and can't mess things up.

Edit: This makes a lot of sense, thanks a lot, this question was really irritating me.

Last edited by _gcx; 1 week ago

0

reply

Report

#6

Maybe slightly nicer is to prove that

#S(jm_k) <= j#S(m_k)

and observe #S(N) <= #S(jm_k) whenever j >= N/m_k to deal with the case where N isn't a multiple of m_k.

It's essentially the same argument but I think it's more elegant (or at least less *inelegant*!)

#S(jm_k) <= j#S(m_k)

and observe #S(N) <= #S(jm_k) whenever j >= N/m_k to deal with the case where N isn't a multiple of m_k.

It's essentially the same argument but I think it's more elegant (or at least less *inelegant*!)

Last edited by DFranklin; 1 week ago

0

reply

(Original post by

Maybe slightly nicer is to prove that

#S(jm_k) <= j#S(m_k)

and observe #S(N) <= #S(jm_k) whenever j >= N/m_k to deal with the case where N isn't a multiple of m_k.

It's essentially the same argument but I think it's more elegant (or at least less *inelegant*!)

**DFranklin**)Maybe slightly nicer is to prove that

#S(jm_k) <= j#S(m_k)

and observe #S(N) <= #S(jm_k) whenever j >= N/m_k to deal with the case where N isn't a multiple of m_k.

It's essentially the same argument but I think it's more elegant (or at least less *inelegant*!)

Don't think it's strictly necessary to go casewise, the fact that we can split up the interval into at most a + 1 (if we write N = am_k + b) blocks of size at most m_k/2^k seems to give a strict enough bound.

Last edited by _gcx; 1 week ago

1

reply

Report

#8

(Original post by

Seems to all check out, thanks. There was a similar idea on a previous sheet about splitting intervals into blocks so I really should've spotted the trick!

Don't think it's strictly necessary to go casewise, the fact that we can split up the interval into at most a + 1 (if we write N = am_k + b) intervals of size at most m_k/2^k seems to give a strict enough bound.

**_gcx**)Seems to all check out, thanks. There was a similar idea on a previous sheet about splitting intervals into blocks so I really should've spotted the trick!

Don't think it's strictly necessary to go casewise, the fact that we can split up the interval into at most a + 1 (if we write N = am_k + b) intervals of size at most m_k/2^k seems to give a strict enough bound.

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top