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

In summary, the conversation discusses the problem of finding the probability that a random integer, modulo the product of given moduli, falls into at least one of a large number of residue classes. The conversation mentions an algorithm for calculating this probability when the moduli are pairwise coprime, but raises the question of what to do when they are not. The possibility of using a program or function for this purpose is also mentioned, as well as the need to consider a certain range of integers and how to handle cases where an integer falls into multiple classes.
  • #1
CRGreathouse
Science Advisor
Homework Helper
2,844
0
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.
 
Physics news on Phys.org
  • #2
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 to How Do You Calculate Probabilities with Non-Coprime Residue Classes?

1. What are residue classes?

Residue classes are sets of integers that are equivalent to each other when divided by a fixed integer. For example, in the residue class modulo 5, the numbers 1, 6, and 11 are all equivalent since they leave the same remainder (1) when divided by 5.

2. How do you combine residue classes?

To combine residue classes, you simply add the corresponding elements together. For example, in the residue class modulo 5, the combination of [1] and [2] would be [3] since 1+2=3.

3. Can you combine residue classes with different moduli?

No, residue classes can only be combined when they have the same modulus. This is because the modulus determines the possible remainders and the equivalence of elements in the residue class.

4. What is the purpose of combining residue classes?

Combining residue classes allows us to simplify complex arithmetic expressions involving integers. It also helps in solving equations and proving certain mathematical theorems.

5. Are there any rules for combining residue classes?

Yes, there are rules for combining residue classes, such as the associative and commutative properties. These rules ensure that the result of combining residue classes is unique and does not depend on the order of operations.

Similar threads

  • Computing and Technology
Replies
11
Views
2K
  • STEM Academic Advising
Replies
4
Views
2K
  • STEM Academic Advising
Replies
13
Views
2K
  • Introductory Physics Homework Help
Replies
6
Views
1K
  • Math Proof Training and Practice
2
Replies
60
Views
8K
  • Poll
  • Science and Math Textbooks
Replies
2
Views
7K
Replies
1
Views
4K
  • Math Proof Training and Practice
6
Replies
175
Views
20K
Replies
2
Views
1K
  • STEM Academic Advising
Replies
10
Views
4K
Back
Top