# What is the probability that a randomly selected positive integer between 1 and 100 (inclusive) is square-free?

What is the probability that a randomly selected positive integer between $1$ and $100$ (inclusive) is square-free (i.e., has no square factor; for instance $15 = 3 \cdot 5$ is square-free, but $90$ is not, since it has a factor of $3^2$).

I have no idea how to solve this problem. Any help on how to proceed?

-
My suggestion would be to count the number of multiples of $4=2^2$, then the number of multiples of $9=3^2$, then the number of multiples of $25=5^2$ (why not multiples of $4^2=16$?) etc. and be sure not to count the ones you've counted previously. How many do you get? What is the probability of getting one of these out of 100? What, then, is the probability of NOT getting one of these when a positive integer is selected out of 100? – Darrin Feb 5 '14 at 5:03
The only square-ful numbers less than 101 that are divisible by the squares of more than one prime are 36, 72, and 100. – Hugh Feb 5 '14 at 6:21

I recommend a variant of the Sieve of Eratosthenes. Instead of crossing off the prime numbers, cross of the perfect squares and their multiples. Count the numbers that you don't cross off to get the square free numbers.

-

First count the numbers which are not squarefree. An integer $n$ is not squarefree if it is a multiple of $4$ or $9$ or $16$ or $25$ or... or $100$, and as you are only interested in numbers up to $100$ we can stop there. However, multiples of $16$ can be ignored as they will already have been counted as multiples of $4$, and so on.

So what it comes down to is that we need to eliminate numbers which are multiples of $4$, $9$, $25$, or $49$. We still have to be careful as for example $36$ is a multiple both of $4$ and of $9$ and we mustn't exclude it twice. The best thing to do is to use the inclusion/exclusion formula.

Let $S_4$ be the set of numbers from $1$ to $100$ which are multiples of $4$, and so on. The number of integers we don't want is \eqalign{|S_4\cup S_9\cup S_{25}\cup S_{49}| &=|S_4|+|S_9|+|S_{25}|+|S_{49}|\cr &\qquad{}-|S_4\cap S_9|-\cdots\cr &\qquad{}+|S_4\cap S_9\cap S_{16}|+\cdots\cr &\qquad{}-|S_4\cap S_9\cap S_{16}\cap S_{25}|\ .\cr} There are "in principle" a lot of terms to work out here, but if you think carefully you will see that many of them are zero. See if you can take it from here.

Comment. For an interesting extension of the problem, see here, equation (8).

-
Thanks for the erudite response, David. I have to get some rest (long day), but I'll work this out tomorrow. If I post my work, mind taking a look at it? Thanks! – Cormano Sanchez Feb 5 '14 at 6:08
If I have time, sure. – David Feb 5 '14 at 6:16

$$\begin{matrix} 1 &2&3&\bf 2^2&5&2\cdot 3&7&\bf 2^3&\bf 3^2&2\cdot 5\\ 11&\bf 2^2\cdot 3&13&2\cdot 7&3\cdot 5&\bf 2^4&17&\bf 3^2\cdot 2&19&\bf 2^2\cdot 5\\ 3\cdot 7&2\cdot 11&23&\bf 2^3\cdot 3&\bf 5^2&2\cdot 13&\bf3^3&\bf 2^2\cdot 7&29&2\cdot 3\cdot 5\\31&\bf 2^5&3\cdot 11&2\cdot 17&5\cdot 7&\bf 2^2\cdot3^2&37&2\cdot 19&3\cdot 13&\bf 2^3\cdot 5\\ 41&2\cdot 3\cdot 7&43&2^2\cdot 11&\bf 3^2\cdot 5&2\cdot 23&47&\bf 2^4\cdot 3&\bf 7^2&\bf 2\cdot 5^2\\ 3\cdot 17&\bf 2^2\cdot 13&53&\bf 2\cdot 3^3&5\cdot 11&\bf 2^3\cdot 7&3\cdot 19&2\cdot 29&59&\bf 2^2\cdot 3\cdot 5\\ 61&2\cdot 31&\bf 3^2\cdot 7&\bf 2^6&5\cdot13&2\cdot 3 \cdot 11&67&\bf 2^2\cdot 17&3\cdot 23&2\cdot 5\cdot 7\\ 71&\bf 2^3\cdot 3^2&73&2\cdot 37&\bf 3\cdot 5^2&\bf 2^2\cdot 19&7\cdot 11&2\cdot 3\cdot 13&79&\bf 2^4\cdot 5\\ 9^2&2\cdot 41&83&\bf 2^2\cdot 3\cdot 7&5\cdot 17&2\cdot 43&3\cdot 29&\bf 2^3\cdot 11&89&\bf3^2\cdot 2\cdot 5\end{matrix}$$

I leave the last row to you.

-
Dear lord.$\ \$ – Mike Miller Feb 5 '14 at 7:05

A number that is not squarefree is a multiple of a $p^2$ for some $p$ prime. The values of $p^2$ that are small enough to divide a number between $1$ and $100$ are $4, 9, 25, 49$.

So, the question becomes: how many numbers from $1$ to $100$ are not multiples of $4$ or $9$ or $25$ or $49$? Count how many there are of each, and make sure you take into account numbers like $36$, which is both a multiple of $4$ and a multiple of $9$.

-