Probability that two integers chosen at random from an arithmetic progression are coprime

247 Views Asked by At

It is well known that every coprime arithmetic progression (AP) contains an infinite number of prime numbers.

And also that the probability of $2$ random integers being coprime is $\dfrac{6}{\pi^2}$.

What is the probability of $2$ integers chosen at random from an admissible AP are coprime?

1

There are 1 best solutions below

8
On BEST ANSWER

Two arbitrary integers $a$ and $b$ are coprime if and only if there is no prime $p$ such that $p|x$ and $p|y$. These conditions are independent, so the probability a given $p$ divides $a$ and $b$ is $p^{-2}$. These conditions are independent as $p$ varies, so the probability $b$ and $b$ are coprime is $$ \prod_p\left(1-p^{-2}\right)=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}. $$ With a little care this probabilistic argument can be made rigorous.

Let $k$ and $n$ be coprime integers. If we restrict $a$ and $b$ to be congruent to $k$ modulo $n$ (where $k$ and $n$ are coprime), then no prime dividing $n$ can divide $a$ or $b$. For $p\nmid n$, the probability $p$ divides $a$ and $b$ is unchanged. So, the probability $a$ and $b$ are coprime is $$ \prod_{p\nmid n}\left(1-p^{-2}\right)=\frac{6}{\pi^2}\prod_{p|n}\left(1-p^{-2}\right)^{-1}. $$