Residue classes

CRGreathouse · 2009-02-12, 20:17

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.

maxal · 2009-03-11, 15:46

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 inclusion-exclusion principle to express the probability for the union in terms of the probabilities for the intersections:
http://en.wikipedia.org/wiki/Inclusi...in_probability

CRGreathouse · 2009-03-12, 14:46

Bingo. Thanks!

fivemack · 2009-03-12, 15:28

Thanks for the Nielsen reference; it's a lovely piece of higher-order 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 ...

CRGreathouse · 2009-03-12, 16:00

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

2009-02-12, 20:17	#1
CRGreathouse Aug 2006 5,987 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Residue and Shift, what do these mean?	king	Information & Answers	1	2018-03-05 05:52
Classes	Dubslow	Lounge	67	2012-12-08 07:46
Quadratic residue mod 2^p-1	alpertron	Miscellaneous Math	17	2012-04-30 15:28
Primes in residual classes	Unregistered	Information & Answers	6	2008-09-11 12:57
Masked residue	schneelocke	PrimeNet	6	2003-11-22 01:26

2009-03-11, 15:46	#2
maxal Feb 2005 2²×5×13 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 inclusion-exclusion principle to express the probability for the union in terms of the probabilities for the intersections: http://en.wikipedia.org/wiki/Inclusi...in_probability

2009-03-12, 14:46	#3
CRGreathouse Aug 2006 5,987 Posts	Bingo. Thanks!

2009-03-12, 15:28	#4
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	Thanks for the Nielsen reference; it's a lovely piece of higher-order 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 ...

2009-03-12, 16:00	#5
CRGreathouse Aug 2006 5,987 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...