What is the Probability of Two Random Numbers Being Coprime?
Theo Macklin
If one were to select two integers at random between one and infinity, what is the likelihood that they would share no factors other than 1? This seems like a question that would venture into the realm of prime numbers or other unresolved questions. However, this question actually leads us along a path through a wide variety of mathematical fields and uses one of the most compelling results in mathematics. To start to find an answer for this question we must first phrase our question in terms of its mathematical operators. To do this we must appreciate that when two numbers are coprime their greatest common denominator is 1. For two integers, and , this expression is as follows:
gcd[ , ] = 1
The gcd function outputs the greatest common factor of its two operators. We can now use probability notation to express the probability of such a state occurring out of 1 (i.e.: 50% chance ≡ 0.5). We will call this probability :
𝑃(gcd[ , ] = 1) =
Let this be result (1)
Now let us consider the alternative possibility: a number 𝑘 is the greatest common denominator of two numbers, and b , where ( , b) > 𝑘 . The likelihood that both numbers are both divisible by 𝑘 is equal to the probability of each number being divisible by 𝑘 multiplied together. Since it is logical to assume that 2 divides half of all numbers, 3 a third, 4 a quarter, 5 a fifth, etc. it is also reasonable to conclude that 𝑘 divides one 𝑘 th of all numbers. Thus:
𝑃(𝑘 𝑖 ℎ ) = 𝑃 ( 𝑘
𝑘
∈ ) × 𝑃 (
∈ )
1 𝑘
1 𝑘
1 𝑘 2
=
×
=
To determine whether 𝑘 is the greatest common denominator of and b we must ensure that:
𝑘
𝑘
gcd [
,
] = 1
As
≡ and
≡ the probability that they are coprime must be, as in result (1) , y .
𝑘
𝑘
𝑃(gcd [
,
] = 1) =
Thus, the probability that 𝑘 is the highest common factor must be:
24
Made with FlippingBook - professional solution for displaying marketing and sales documents online