[number theory] sieving with a_i mod p_i

[jaydfox]

{0 mod 2, 0 mod 3 , 0 mod 5 , ... 0 mod prime 't' } does not define a certain a mod b.

Rather it sieves out possibilities of a mod b.

Its like 0 mod 2 , 0 mod 3 , 0 mod 5 gives :

1,7,11,13,17,19,23,29 mod 30.

A similar thing happens with a_i mod p_i.

But maybe that is what you actually meant (to say).

regards

tommy1729

Hmm, maybe we're talking about different things. I'm talking about an a_i that gives the respective remainders mod p_i, all at the same time, not individually. I agree that for sieving, we care about a single match, so we get back a set of sieved (or unsieved) numbers.

The only numbers that are 0 mod 2, 0 mod 3, 0 mod 5 (all at the same time, not individually) are the numbers that are 0 mod 30. The only numbers that are 1 mod 2, 2 mod 3, 1 mod 5 are the numbers that are 11 mod 30. So by giving me a set of a_i's to go with the p_i's, like a_i={1, 2, 1} and p_i={2, 3, 5}, I can give you back a new "a" to go with product(p_i): a=11 and primorial(5)=30.

In this sense, giving me a set of a_i's in the range 0 <= a_i < p_i is just equivalent to giving me a fixed a in the range 0 <= a < primorial(max(p_i))

In light of this, then yes, having unfixed a_i's is an interesting problem in its own right, as long as we can agree that it's just another way of looking at a fixed value of a.

Edit: So for example, sieving numbers against 1 mod 2, 2 mod 3, and 1 mod 5, is like sieving them against 11 mod 2, 11 mod 3, and 11 mod 5. Hopefully that made sense...End Edit

And I reserve the right to be wrong.