1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ what about $p|k$? $\endgroup$ – JMP Oct 10 '15 at 0:22
  • 1
    $\begingroup$ If $p|k$ (but $p\nmid n$), it is still true that an integer congruent to $k$ mod $n$ is divisible by $p$ with probability $1/p$. In this sense primes dividing $k$ are no different than other primes that don't divide $n$. $\endgroup$ – Julian Rosen Oct 10 '15 at 0:25
  • 1
    $\begingroup$ Adding to Julian Rosen's comment: the AP represented by $k$ is also represented by $n+k$, and none of the primes dividing $k$ also divide $n+k$. Moral: don't try to work with divisibility properties of representatives of residue classes. Only the primes dividing the modulus matter. (Example: modulo 15, it doesn't make sense to say some residue classes are even or odd.) $\endgroup$ – Greg Martin Oct 10 '15 at 0:57
  • $\begingroup$ @GregMartin; is it because $3\mod15$ e.g. is odd/even/odd/even...($3,18,33,48,...$) $\endgroup$ – JMP Oct 10 '15 at 1:10
  • $\begingroup$ so if i consider $1,3,5,7\mod8$ then $k$ makes no difference? $\endgroup$ – JMP Oct 10 '15 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.