Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2009-02-12, 20:17   #1
CRGreathouse's Avatar
Aug 2006

2·29·103 Posts
Default 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.
CRGreathouse is offline   Reply With Quote
Old 2009-03-11, 15:46   #2
maxal's Avatar
Feb 2005

22·32·7 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:
maxal is offline   Reply With Quote
Old 2009-03-12, 14:46   #3
CRGreathouse's Avatar
Aug 2006

597410 Posts

Bingo. Thanks!
CRGreathouse is offline   Reply With Quote
Old 2009-03-12, 15:28   #4
(loop (#_fork))
fivemack's Avatar
Feb 2006
Cambridge, England

2×3,191 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 ...
fivemack is offline   Reply With Quote
Old 2009-03-12, 16:00   #5
CRGreathouse's Avatar
Aug 2006

2×29×103 Posts

Did you see the video abstract?

I thought it was neat to see Neilsen actually explaining it himself...
CRGreathouse is offline   Reply With Quote

Thread Tools

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

All times are UTC. The time now is 15:08.

Sun Mar 7 15:08:39 UTC 2021 up 94 days, 11:19, 0 users, load averages: 1.82, 1.61, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.