Associated Topics || Dr. Math Home || Search Dr. Math

### Probability that a Random Integer...

```
Date: 7/18/96 at 2:42:49
From: don mcmahon&sheri anderson
Subject: Probability that a Random Integer...

I started trying to figure out what the probability that an integer
chosen randomly would be an integer multiple of a given integer "n"
(or perhaps of a prime "p")...and then the probability that it would
be a multiple of, say, the integers 2...7, and so on. I think I got
stuck on trying to figure out how to formulate  the "or" probabilities
and add things up properly. I think my idea was to generate a sequence
P(n) where P(n) would be the probability a random integer would be a
multiple of at least one of the integers from 2 up to n. I think I got
tangled up in the lattice of integers and then had to go settle a
civil war in the sandbox in the backyard. Can you head me in the
right direction?

Sheri Anderson
```

```
Date: 7/18/96 at 19:58:55
From: Doctor Tom
Subject: Re: Probability that Random Integer...

Well, to be precise (and that's what we mathematicians have to be!),
I have to know exactly what you mean by "an integer chosen randomly".

If you're talking about the entire infinite set of integers, there is
no way to do this without some sort of a distribution function over
the integers, and there is no such function that gives an "equal
probability" for all integers.

To make things precise, here's what I'll assume you mean:  If M is
a very large integer, and we randomly (with equal probability)
choose an integer between 0 and M, what's the probability that it
is divisible by n?  For any fixed M, you can work this out, and then
if we take the limit of these probabilities as M goes to infinity,
I think that will be what you want.

So if your question just concerns a single number n, the answer is
that the limiting probability is 1/n.  For large M, roughly 1/n of
the integers less than M are divisible by n, and the error is smaller
and smaller as M gets larger and larger.

If you ask, "What's the probability that a number is divisible by
n and m?", I think you begin to see the problem - for example, if
n = 2 and m = 4, it's 1/4, since anything divisible by 4 is
automatically divisible by 2.

If you ask the general question, "What's the probability that a number
is divisible by all of the numbers n1, n2, n3, ..., nx?" the answer is
"if z = the least common multiple of n1, n2, ..., nx, then the
probability is 1/z".

The least common multiple of a set of integers is the smallest integer
that all of them divide.  For example, the least common multiple
of 4 and 6 is 12.  Of 7 and 11 is 77.  And so on.

To find the least common multiple of a set of numbers, factor all of
them into prime factors.  For each prime that appears anywhere in the
list, find the number in which the highest power of that prime
appears, and include that power of the prime in a product.

The grand product is the LCM (least common multiple).

For example, to find the LCM of 24, 125, 32, 100, and 444, where
"*" indicates multiplication, and "^" exponentiation:

24 = 2^3*3^1
125 = 5^3
32 = 2^5
100 = 2^2*5^2
444 = 2^2*3^1*37^1

LCM = 2^5*3^1*5^3*37^1

I hope it's obvious why this works, and I won't bother to multiply
out the number in my example.

-Doctor Tom,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search