Q. 5.32 - A First Course in Probability

Question

 Let X and Y be independent random variables that are both equally likely to be either 1, 2, . . . ,(10)N, where N is very large. Let D denote the greatest common divisor of X and Y, and let Q k = P{D = k}. 

(a) Give a heuristic argument that Q k = 1 k2 Q1. Hint: Note that in order for D to equal k, k must divide both X and Y and also X/k, and Y/k must be relatively prime. (That is, X/k, and Y/k must have a greatest common divisor equal to 1.) (b) Use part (a) to show that Q1 = P{X and Y are relatively prime} = 1 q k=1 1/k2 It is a well-known identity that !q 1 1/k2 = π2/6, so Q1 = 6/π2. (In number theory, this is known as the Legendre theorem.) (c) Now argue that Q1 = "q i=1  P2 i − 1 P2 i  where Pi is the smallest prime greater than 1. Hint: X and Y will be relatively prime if they have no common prime factors. Hence, from part (b), we see that Problem 11 of Chapter 4 is that X and Y are relatively prime if XY has no multiple prime factors.) 

Step-by-Step Solution

Answer

To acquire the stated, use basic properties from number theory and probability.

Step:1 Given information

Let X and Y be independent random variables with equal chances of being $1, 2,...,\left(10\right)N$, where N is a very high number. Let D be the greatest common divisor of X and Y, and $Q k = PD = k$be the greatest common divisor of X and Y.

Step:2 Explanation of the solution

(a) $D=K$ is true if and only if $K/X$and $K/Y$ are true, and $GCD(X/K, Y/K) =1$. These events are unrelated because X and Y are unrelated. Because every k is divisible by k, the probability of the first two events is 1/K. According to the definition, the probability of the last event is equal to Q1.

(b) Keep in mind that events $D=K$ for $k=1,2,...$ are mutually discontinuous and cover the whole probability space. This is due to the fact that every pair of numbers has the largest common divisor. We can deduce from section (a) that

Applying sum $\sum _{k=1}^{\infty }$ to the both sides, we have that

$\sum _{k=1}^{\infty }{Q}_k=Q_1\sum _{k=1}^{\infty }\frac{1}{k^2}$

However, because of the discussion above, the number on the left side is equal to one. Hence

$Q_1=\frac{1}{{\sum }_{k=1}^{\infty }\frac{1}{k^2}}$

Step: 3 Evaluation

Prime number $P_i$ divides both X and Y with probability $\frac{1}{p_i^2}$

The probability $P_i$ does not divides both X and Y is $\begin{array}{r}=1-\frac{1}{p_i^2}\\ =\frac{p_i^2-1}{p_i^2}\\ Q_1=P\left(\underset{i=1}{\overset{\mathrm{\infty }}{\cap }} \left\{P_i\text{ does not divide both }X\text{ and }Y\right\}\right)\\ Q_1=\prod _{i=1}^{\mathrm{\infty }} \left(\frac{P_i^2-1}{P_i^2}\right)\end{array}$

As a result, X and Y are relatively prime if neither of the prime numbers divides both X and Y. We have that because every prime number divides both X and Y independently of every other prime number.

so we have proved the claimed.