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?(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Combining residue classes

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**