How to calculate divisibility with 3 of a ratio?

Question

Given the equation $k = (p - 1)/2$ where $p$ is any prime number, what is the chance that a randomly chosen element from the set of all $k$s will be divisible by 3? Or rather, how can this probability calculated?

Answer 1

First of all, this set of integers $k$ is infinite (since there are infinitely many primes), and there is no uniform probability measure on a countably infinite set. So one needs to specify what probability distribution is intended.

The usual interpretation is to consider the set of all such integers $k$ up to $x$ for some parameter $x$, calculate or estimate the probability (as a function of $x$), and then take the limit as $x\to\infty$.

Here, $k$ is divisible by $3$ precisely when $p=2k+1$ is congruent to $1\pmod 6$. It is known that the number of primes up to $x$ is roughly $x/\log x$, and the number of primes congruent to $1\pmod 6$ up to $x$ is roughly $x/2\log x$. This means that the probability, as a function of $x$, is roughly $1/2$.

Using more rigorous statements (see the prime number theorem for arithmetic progressions), you can prove that the limiting probability is indeed exactly $1/2$.

Answer 2

Every prime number other than $2$ and $3$ is congruent to either $1$ or $5$ modulo $6$. If a $p\equiv1\pmod{6}$ then $k$ is divisible by $3$. if $p\equiv5\pmod{6}$ then $k$ is not divisible by $3$.

By Chebotarevs density theorem the proportion of primes in each of the two congruence classes is asymptotically equal, meaning that in a naive sense your probability is $\frac{1}{2}$. The naive part skips over the problem of choosing primes randomly.