20090212, 20:17  #1 
Aug 2006
13524_{8} Posts 
Residue classes
Suppose I had a lot of residue classes and I wanted to find the probability that a random integer (mod the product of the moduli) was in at least one of the classes. How could I calculate that?
If the moduli were pairwise coprime, it would be easy: start an accumulator at 0 and for each class a mod m, calculate acc < acc + 1/m  acc/m and return the accumulator. But what if they're not? And what if there are a whole lot of residue classes, and their moduli are both large and fairly smooth (so they are 'far from' being coprime)? I'm picturing some kind of solution involving tracking products of small primes separately and using some version of the above algorithm for the large, and so probably coprime to everything else, prime factors. But is there a better way? Is there already a program/function/library that can do this for me? I'm actually reminded of a recent preprint by Neilsen ('a covering set with minimum modulus 40' or something like that), though this is by no means a covering set. 
20090311, 15:46  #2 
Feb 2005
252_{10} Posts 
In other words, you need to find the probability of random integer to belong to the union of given residue classes.
As it is easy to find probability that a random integer belongs to the intersection of residue classes (which would be 0 or 1/L where L is l.c.m. of the moduli, depending on whether this intersection is empty), just use the inclusionexclusion principle to express the probability for the union in terms of the probabilities for the intersections: http://en.wikipedia.org/wiki/Inclusi...in_probability 
20090312, 14:46  #3 
Aug 2006
1011101010100_{2} Posts 
Bingo. Thanks!

20090312, 15:28  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
2·3,191 Posts 
Thanks for the Nielsen reference; it's a lovely piece of higherorder abstraction.
0(2) 1(4) 0(5) 0(7) 3(8) 1(10) 1(14) 3(20) 3(28) 2(35) 39(40) 39(56) 27(70) 47(140) seems to be a covering with all moduli coprime to 3 ... 
20090312, 16:00  #5 
Aug 2006
2^{2}·1,493 Posts 
Did you see the video abstract?
http://www.youtube.com/watch?v=3ev1YjVl0RY I thought it was neat to see Neilsen actually explaining it himself... 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Residue and Shift, what do these mean?  king  Information & Answers  1  20180305 05:52 
Classes  Dubslow  Lounge  67  20121208 07:46 
Quadratic residue mod 2^p1  alpertron  Miscellaneous Math  17  20120430 15:28 
Primes in residual classes  Unregistered  Information & Answers  6  20080911 12:57 
Masked residue  schneelocke  PrimeNet  6  20031122 01:26 