# Probability of highest common factor in Williams

In David Williams’ Probability with Martingales, $\exists$ this exercise.

Let $s > 1$ and let $\zeta(s) = \sum_{n=1}^\infty n^{-s}$.

Let $X$ and $Y$ be independent $\mathbb{N}$-valued random variables with $P(X=n)=P(Y=n)=\dfrac{n^{-s}}{\zeta(s)}$.

Facts:

1 The events ($E_p$: $p$ prime) where $E_p =$ ($X$ is divisible by $p$) (This time $p$ may not be prime) are independent.

2 The events ($F_p$: $p$ prime) where $F_p =$ ($Y$ is divisible by $p$) (This time $p$ may not be prime) are independent.

3 $P(E_p) = p^{-s}$

4 This is Euler’s formula $1/\zeta(s) = \prod_p (1-1/p^s)$ where $p$ is prime.

5 $P(X=1) = 1/\zeta(s) = \prod_p (1-1/p^s)$

6 $P(\text{no square other than 1 divides }X)= \dfrac{1}{\zeta(2s)}$

Here is the exercise:

Let $H$ be the highest common factor of $X$ and $Y$. Prove that $P(H=n) = \dfrac{n^{-2s}}{\zeta(2s)}$.

How do I go about doing this? I know $H$ divides both $X$ and $Y$ but that’s just making use of the fact that $H$ is a common factor. Since it is the highest, all the natural numbers greater than $H$ do not divide $X$ and $Y$ or something like that?

#### Solutions Collecting From Web of "Probability of highest common factor in Williams"

I don’t really understand what you mean in facts 1 and 2, about $p$ being prime but may not be prime. But anyway:
\begin{align*}
P(H=n) &= \sum_{\substack{c,d\in\Bbb N \\ \gcd(c,d)=n}} P(X=c)P(Y=d) \\
&= \sum_{\substack{a,b\in\Bbb N \\ \gcd(a,b)=1}} P(X=na)P(Y=nb) \\
&= \sum_{\substack{a,b\in\Bbb N \\ \gcd(a,b)=1}} \frac{(na)^{-s}}{\zeta(s)}\frac{(nb)^{-s}}{\zeta(s)} \\
&= n^{-2s} \sum_{\substack{a,b\in\Bbb N \\ \gcd(a,b)=1}} \frac{a^{-s}}{\zeta(s)}\frac{b^{-s}}{\zeta(s)} \\
&= n^{-2s} \sum_{\substack{a,b\in\Bbb N \\ \gcd(a,b)=1}} P(X=a)P(Y=b) = n^{-2s} P(H=1).
\end{align*}
Therefore
$$1 = \sum_{n=1}^\infty P(H=n) = \sum_{n=1}^\infty n^{-2s} P(H=1) = \zeta(2s)P(H=1),$$
and the desired result follows.