Question

(a) An integer $N$is to be selected at random from $\left\{1,2,\dots ,(10{)}^3\right\}$in the sense that each integer has the same probability of being selected. What is the probability that $N$will be divisible by $3$? by $5$? by $7$? by $15$? by $105$? How would your answer change if $(10{)}^3$is replaced by $(10{)}^k$as $k$became larger and larger?

(b) An important function in number theory-one whose properties can be shown to be related to what is probably the most important unsolved problem of mathematics, the Riemann hypothesis - is the Möbius function $\mu \left(n\right)$, defined for all positive integral values $n$as follows: Factor $n$into its prime factors. If there is a repeated prime factor, as in $12=2·2·3$or $49=7·7$, then $\mu \left(n\right)$is defined to equal $0$. Now let $N$be chosen at random from $\left\{1,2,\dots (10{)}^k\right\}$, where $k$is large. Determine $P\left\{\mu \right(N)=0\}$as $k\to \infty$. Hint: To compute $P\left\{\mu \right(N)\ne 0\}$, use the identity

$\prod _{i=1}^{\infty }\frac{P_i^2-1}{P_i^2}=\left(\frac{3}{4}\right)\left(\frac{8}{9}\right)\left(\frac{24}{25}\right)\left(\frac{48}{49}\right)\cdots =\frac{6}{{\pi }^2}$

where $P_i$is the $i$ th-smallest prime. (The number $1$ is not a prime.)

Short answer

1. The ratio of divisible numbers $i$gets closer and closer on the limit gets closer and closer $P(N\%i=0)\approx \frac{1}{i}$
2. The third equality is in fact an approximation since we have that $N$is a very large number, so we can consider all primes, not only that are less or equal to $N$.

Step-by-step solution

Given information Part (a) 

Each integer has the same probability of being selected.

We have to consider numbers $1,2,\dots ,{10}^3$. Every third number out of them is divisible by $3$, so there exist $333$numbers that are divisible by three. Hence

$P(N\%3=0)=\frac{333}{1000}$

Calculation Part (a)  

Using the similar argument, we have

$P(N\%5=0)=\frac{200}{1000}$

$P(N\%7=0)=\frac{142}{1000}$

$P(N\%15=0)=\frac{66}{1000}$

$P(N\%105=0)=\frac{9}{1000}$

Final answer Part (a)  

If we apply a limit to these probabilities as $k$gets better and bigger, we could have

$P(N\%i=0)\to \frac{1}{i}$

since the ratio of divisible numbers $i$gets closer and closer on the limit gets closer and closer $1/i$.

Given information Part (b)  

$\prod _{i=1}^{\infty }\frac{P_i^2-1}{P_i^2}=\left(\frac{3}{4}\right)\left(\frac{8}{9}\right)\left(\frac{24}{25}\right)\left(\frac{48}{49}\right)\cdots =\frac{6}{{\pi }^2}$

Calculation Part (b)  

Observe that number $N$has not double primes in its factorization if and only if it is not divisible by any square of prime number. Hence

$P\left(\mu \right(N)=0)=P\left(N\%p_i^2\ne 0,\text{for all}{p}_{-}i\text{less or equal to}N\right)$

$=\prod _{p_i\le N}P\left(N\%p_i^2\ne 0\right)$

$=\prod _{p_i}\left[1-P\left(N\%p_i^2=0\right)\right]$

$=\prod _{p_i}\left(1-\frac{1}{p_i^2}\right)$

$=\prod _{p_i}\frac{p_i^2-1}{p_i^2}=\frac{6}{{\pi }^2}$

where the third equality is in fact an approximation since we have that $N$ is very large number, so we can consider all primes, not only that are less or equal to $N$.

Final Answer Part (b)

The third equality is in fact an approximation since we have that $N$is a very large number, so we can consider all primes, not only that are less or equal to localid="1647535575561" $N.$$N$