Probability of Four Random Integers Having a Common Factor

Problem

Question: Probability of Four Random Integers Having a Common Factor

Solution

As in a sister page, the probability of an integer to be even, i.e., to be divisible by $2$ is $\displaystyle \frac{1}{2}.$ The probability of four numbers bing even is $\displaystyle \left(\frac{1}{2}\right)^4.$ Thus the probability that at least of the four numbers is odd is $\displaystyle 1- \left(\frac{1}{2}\right)^4.$

Similarly, the probability that at least one of four random integers is not divisible by $3$ is $\displaystyle 1- \left(\frac{1}{3}\right)^4.$ For any other prime that's $\displaystyle 1- \left(\frac{1}{p}\right)^4.$

Since divisibility by one prime number is independent of divisibility by any other prime number, four random numbers have no common factor with the probability of $\displaystyle \prod_{p\text{ prime}} \left[1- \left(\frac{1}{p}\right)^4\right].$ It follows that the probability of four random numbers to have a common factor is

$\displaystyle 1-\prod_{p\text{ prime}} \left[1- \left(\frac{1}{p}\right)^4\right].$

A Rational Estimate

The sum $\displaystyle \sum_{k=1}^{\infty}\frac{1}{k^s}$ is known as a zeta-function $\zeta(s)$ many of whose values are known specifically. In particular, $\zeta(4)=\displaystyle \frac{\pi^4}{90}.$ Below, we'll find some rational estimates directly. We'll start with a special case of the Euler/Kronecker formula:

$\displaystyle\small{\frac{1}{\displaystyle (1-2^{-4})(1-3^{-4})(1-5^{-4})(1-7^{-4})\cdots}=1+\frac{1}{2^4}+\frac{1}{3^4}+\frac{1}{4^4}+\frac{1}{5^4}+\ldots=\sum_{k=1}^{\infty}\frac{1}{k^4}}.$

Now, we group the terms on the right by the powers of $2:$

$\displaystyle\begin{align} \sum_{k=1}^{\infty}\frac{1}{k^4}&=1+\left(\frac{1}{2^4}+\frac{1}{3^4}\right)+\left(\frac{1}{4^4}+\frac{1}{5^4}+\frac{1}{6^4}+\frac{1}{7^4}\right)+\ldots\\ &\lt 1+\left(\frac{1}{2^4}+\frac{1}{2^4}\right)+\left(\frac{1}{4^4}+\frac{1}{4^4}+\frac{1}{4^4}+\frac{1}{4^4}\right)+\ldots\\ &=1+2\cdot\frac{1}{2^4}+4\cdot\frac{1}{4^4}+8\cdot\frac{1}{8^4}+\ldots\\ &=1+\frac{1}{2^3}+\frac{1}{4^3}+\frac{1}{8^3}+\ldots=\frac{1}{\displaystyle 1-\frac{1}{8}}=\frac{8}{7}. \end{align}$

On the other hand,

$\displaystyle\begin{align} \sum_{k=1}^{\infty}\frac{1}{k^4}&=1+\frac{1}{2^4}+\left(\frac{1}{3^4}+\frac{1}{4^4}\right)+\left(\frac{1}{5^4}+\frac{1}{6^4}+\frac{1}{7^4}+\frac{1}{8^4}\right)+\ldots\\ &\gt 1+\frac{1}{2^4}+\left(\frac{1}{4^4}+\frac{1}{4^4}\right)+\left(\frac{1}{8^4}+\frac{1}{8^4}+\frac{1}{8^4}+\frac{1}{8^4}\right)+\ldots\\ &= 1+\frac{1}{2^4}+\frac{1}{2}\left(4\cdot\frac{1}{4^4}+8\cdot\frac{1}{8^4}+\ldots\right)\\ &=1+\frac{1}{2^4}+\frac{1}{2}\left(\frac{1}{4^3}+\frac{1}{8^3}+\ldots\right)=1+\frac{1}{2^4}+\sum_{k=2}^{\infty}\frac{1}{2^{3k+1}}\\ &=1+\sum_{k=1}^{\infty}\frac{1}{2^{3k+1}}=1+\frac{1}{16}\cdot\frac{1}{\displaystyle 1-\frac{1}{8}}=\frac{15}{14}. \end{align}$

We found that

$\displaystyle \frac{8}{7}\lt \left(\prod_{p\text{ prime}} \left[1- \left(\frac{1}{p}\right)^4\right]\right)^{-1}\lt \frac{15}{14}$

so that

$\displaystyle 1-\frac{14}{15}\lt 1-\prod_{p\text{ prime}} \left[1- \left(\frac{1}{p}\right)^4\right]\lt 1-\frac{7}{8}$

i.e

$\displaystyle \frac{1}{15}\lt 1-\prod_{p\text{ prime}} \left[1- \left(\frac{1}{p}\right)^4\right]\lt \frac{1}{8}.$

So, the sought probability of four random integers having a common factor is between $\displaystyle \frac{1}{15}$ and $\displaystyle \frac{1}{8}.$

Solution 2

The probability that the $i^{th}$ prime $p_i$ divides an integer is $1/p_i$. Thus, the probability that a $p_i$ divides all four integers chosen is $1/p_i^4$, and the probability that $p_i$ is not a common factor of the four integers is $1-1/p_i^4$. Hence, the desired probability is

$\displaystyle \lim_{n\rightarrow\infty}\left[1-\prod_{i=1}^{n}\left(1-\frac{1}{p_i^4}\right)\right] =1-\frac{1}{\zeta(4)}=1-\frac{90}{\pi^4}\sim 0.076.$

Acknowledgment

The problem comes from the book Challenging Mathematical Problems with Elementary Solutions by A. M. Yaglom and I. M. Yaglom (Vol I, Dover, 1987). The rational approximation is part of their solution. Solution to is by Amit Itagi.

 

|Contact| |Front page| |Contents| |Algebra| |Probability| |Store|

Copyright © 1996-2018 Alexander Bogomolny

 63414828

Search by google: