Probability that the a square-free number is divisible by a given prime number $p.$

481 Views Asked by At

Probability that the a square-free number $n$ is divisible by a given prime number $p$ is $1/(p+1).$

I know that $n$ is square-free and number of square-free integers up-to $x$ is $$ \approx x \prod_{p} \left(1-\frac{1}{p^2}\right) $$ Somehow I need to modify this to count the number that are divisible by $p.$

1

There are 1 best solutions below

5
On BEST ANSWER

Outline: Let $F(t)$ be the number of square-free numbers $\le t$. For large $t$, this is "approximately" $\frac{6}{\pi^2} t$.

We use an Inclusion/Exclusion argument. A first step to an answer is that the number of square-free numbers $\le x$ that are multiples of $p$ is approximately $F(x/p)$. For multiplying a square-free number $\le x/p$ by $p$ yields (for sure) a multiple of $p$ that is $\le x$. It also yields a number which is "usually" square-free. The only perfect square that could possibly divide $py$, where $y\le x/p$ and $y$ is square-free is $p^2$.

Thus $F(x/p)$ overcounts our set of multiples of $p$ that are $\le x$ and square-free. To correct, we must subtract approximately $F(x/p^2)$, which (almost) counts the number of numbers $\le x$ that are divisible by $p^2$ but are otherwise square-free.

We have subtracted too much, for we have subtracted one too many tines the numbers $\le x$ that are divisible by $p^3$ but are otherwise square-free. So we need to add back approximately $F(x/p^3)$, and so on.

The sum of the infinite geometric series $\frac{1}{p}-\frac{1}{p^2}+\frac{1}{p^3}-\frac{1}{p^4}+\cdots$ is $\frac{1}{p}\cdot \frac{1}{1-(-1/p)}$.