Combining residue classes

  • #1
CRGreathouse
Science Advisor
Homework Helper
2,820
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
13,215
10,111
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.
 

Related Threads on Combining residue classes

Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
3K
Replies
8
Views
6K
Replies
3
Views
2K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
1
Views
2K
Top