How Do You Calculate Probabilities with Non-Coprime Residue Classes?

[CRGreathouse]

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.

 

[fresh_42]

The probability is zero, because there are infinitely many integers and only finitely many elements in the classes. I assume you will need to consider only a certain range of integers. Depending on the size of this range you can calculate the probabilities by counting elements and taking the quotient, the relative frequency.

In case your modules or not coprime, you will find integers which fit in more than one class. So you also need a rule of how to proceed (count) in these cases.