The probability of coprimality

A famous result: Two positive integers chosen at random will be coprime with probability {6/\pi^2}.

One has to say what one means by this, since there is no uniform distribution on the positive integers. What we mean is that if we choose {x} and {y} uniformly and independently at random from the integers {\{1,\ldots,N\}}, then {x} and {y} will be coprime with probability tending to {6/\pi^2} as {N\rightarrow\infty}.

Here is one classic proof: Consider the points {(x,y)\in\{1,\ldots,N\}^2} such that {\gcd(x,y)=1}. If we scale this picture by {M}, we will have exactly the points {(X,Y)\in\{1,\ldots,MN\}^2} such that {\gcd(X,Y)=M}. Therefore, whatever the limiting probability {P} of being coprime is, the probability of having {\gcd = M} is exactly {P/M^2}. The law of total probability then implies

\displaystyle  1 = \lim_{N\rightarrow\infty}\mathbf{P}(\gcd(x,y)\in\mathbf{N}) = P \sum_{M=1} \frac{1}{M^2} = P\,\zeta(2).

Another way of imagining a random element on a noncompact group {G} is to look at the profinite completion {\hat{G}}, which is always compact so always possesses a uniform distribution. Now by the Chinese Remainder Theorem,

\displaystyle  \hat{\mathbf{Z}} = \prod_p \mathbf{Z}_p,

so choosing an element at random from {\hat{\mathbf{Z}}} is the same as choosing an element at random from {\mathbf{Z}_p} for each {p}. The probability that a random element of {\mathbf{Z}_p} is divisible by {p} is precisely {1/p}, so the probably that two elements from {\hat{\mathbf{Z}}} are coprime is precisely

\displaystyle  \prod_p (1-1/p^2) = 1/\zeta(2).

This does not imply the asymtotic result in {\mathbf{Z}} mentioned above, but it is a nice way of thinking about it.

EDIT (28/4/12): As pointed out to me by Freddie Manners, the “classic proof” suggested above suffers from the fatal defect of not proving that the limit exists. Here is an alternative proof which does prove that the limit exists. More generally, let {d>1} and consider positive integers {x_1,\ldots,x_d\leq X} chosen uniformly at random. Let {G(X)} be the number of {(x_1,\ldots,x_d)\in[1,X]^d} such that {\gcd(x_1,\ldots,x_d)=1}, and observe that the number of {(x_1,\ldots,x_d)\in[1,X]^d} such that {\gcd(x_1,\ldots,x_d) = n} is precisely {G(X/n)}. Then

\displaystyle  \lfloor X\rfloor^d = \sum_{n\geq1} G(X/n)

for all {X}. Inverting this relationship,

\displaystyle  G(X) = \sum_{n\geq1} \mu(n) \lfloor X/n\rfloor^d.

Thus, the probability that {d} randomly and uniformly chosen integers {x_1,\ldots,x_d\leq X} are all coprime is exactly

\displaystyle P(X) = \sum_{n\geq1} \mu(n) \left(\frac{\lfloor X/n\rfloor}{\lfloor X\rfloor}\right)^d.

The {n}th term here is bounded by {n^{-d}}, so by the dominated convergence theorem {P(X)\rightarrow\sum_{n\geq1} \mu(n) n^{-d} = \zeta(d)^{-1}}.

Rationals are repeating p-adics

I’ve been amusing myself with {p}-adic arithmetic lately: I’ve never really got to know it until now.

We are all familiar with the fact that every {q\in\mathbf{Q}} gets represented in {\mathbf{R}} as a repeating decimal, or whatever your favourite base is. (Here I count terminating decimals as decimals which eventually repeat {000...}.) The converse is of course true as well: repeating decimals are rationals.

Is this true in {\mathbf{Q}_p} as well? That is, are the rationals precisely those {p}-adics which are eventually repeating (in the other direction, of course)? One direction, that repeating {p}-adics are rational, is pretty obvious: if {a\in p^{-t}\mathbf{Z}} and {b\in\mathbf{Z}} then

\displaystyle  a + b p^r + b p^{r+s} + b p^{r+2s} + \cdots = a + b \frac{p^r}{1 - p^s}

is rational. What about the converse?

The converse seems trickier. How again did we do it in {\mathbf{R}}? I don’t even remember: it’s one of those things that we know so fundamentally (until very recently, {\mathbf{Q}} was almost defined in my brain as the reals which eventually repeat) that we forget how to prove it.

Who cares how to prove it? It is true, and it says, in base {p}, that if {q\in\mathbf{Q}} then there exists {a\in p^{-t}\mathbf{Z}} and {b\in\mathbf{Z}} such that

\displaystyle  q = a + b p^r + b p^{r-s} + b p^{r-2s} + \cdots = a + b \frac{p^r}{1 - p^{-s}}.

But hey, this implies that

\displaystyle  q = a - b \frac{p^{r+s}}{1 - p^s},

which we already know is a repeating {p}-adic.