Number of squarefree positive integers less than $100$

$\begingroup$

An integer is called squarefree if it is not divisible by the square of a positive integer greater than $1$. Find the number of squarefree positive integers less than $100$.

My attempt: I apply the inclusion-exclusion principle directly.

• Total number of integers = 99
• Number of integers divisible by $2^2$ = $24$
• Number of integers divisible by $3^2$ = $11$
• Number of integers divisible by $4^2$ = $6$
• Number of integers divisible by $5^2$ = $3$
• Number of integers divisible by $6^2$ = $2$
• Number of integers divisible by $7^2$ = $2$
• Number of integers divisible by $8^2$ = $1$
• Number of integers divisible by $9^2$ = $1$
• Number of integers divisible by $2^2$ and $3^2$ = $2$
• Number of integers divisible by $2^2$ and $4^2$ = $1$

Then the required solution would be $99-(24+11+6+3+2+2+1+1)+2+1=52$. But the solution is $61$. Where is my mistake?

$\endgroup$ 3

4 Answers

$\begingroup$

An integer is square-free if and only if none of its prime factors appear with an exponent $\ge 2$ in its prime factorization.

The only primes that can appear with an exponent of 2 or more in a number less than $100$ are those that are less than $\sqrt{100}=10$, that is, $2$, $3$, $5$, and $7$.

So the numbers you need to exclude are just those that are multiples of $4$, $9$, $25$ or $49$.

Neither of the multiples of $25$ and $49$ are multiples of any of the other squares, so they can be subtracted separately. All we need to care about is the double-counting of multiples of $36$, so:

• Start with $99$ possible numbers.
• Subtract $24$ multiples of $4$.
• Subtract $11$ multiples of $9$.
• Add back $2$ because $36$ and $72$ were each subtracted twice.
• Subtract $3$ multiples of $25$.
• Subtract $2$ multiples of $49$.

$$ 99 - 24 - 11 + 2 - 3 - 2 = 61 $$

$\endgroup$ $\begingroup$

If $4^2$ divides $n$ then so does $2^2$, so your method double-counts. A number is nonsquarefree iff it is divisible by a square of a prime, so we can proceed as follows:

Let $A_k$ denote the numbers (here, positive integers) less than $100$ divisible by $k^2$. Since $$ |A_k| = \left\lfloor \frac{100 - 1}{k^2} \right\rfloor ,$$ we have $|A_k| = 0$ for $k \geq 10$. Then, applying the inclusion-exclusion principle to the sets $A_p$, $p < 10$ prime, gives that the number of nonsquarefree numbers less than $100$ is

\begin{multline}|A_2| + |A_3| + |A_5| + |A_7| \\- (|A_2 \cap A_3| + |A_2 \cap A_5| + |A_2 \cap A_7| + |A_3 \cap A_5| + |A_3 \cap A_7| + |A_5 \cap A_7|) + \cdots ,\end{multline} where $\cdots$ denotes terms containing cardinalities of intersections of three and four sets.

Now, $n \in A_q \cap A_{q'}$ for $q, q'$ coprime iff $n$ is divisible by both $q^2$ and $(q')^2$, and hence by coprimality, by $q^2 (q')^2 = (qq')^2$, so $A_q \cap A_{q'} = A_{qq'}$. So, for example, $A_2 \cap A_5 = A_{10}$, which by the above is empty, and the same is true for all of the intersections of two sets except $A_2 \cap A_3 = A_6$. Similarly, by induction, the triple and quadruple intersections are all empty. This leaves that the number of nonsquarefree numbers less than $100$ is $$|A_2| + |A_3| + |A_5| + |A_7| - |A_6| .$$

$\endgroup$ $\begingroup$

Something that may come in handy if you don't need the exact number of squarefree positive integers equal to or below $n$ and an approximation is sufficient: if we denote by $S(n)$ this quantity, we have:

$$ S(n) \approx \frac{n}{\zeta(2)}, $$

where $\zeta$ denotes the Riemann zeta function and

$$ \zeta(n) = \frac{\pi^2}{6} \approx 1.64493406684822\ldots $$

So in your case the number of positive integers that are squarefree below $100$ is

$$ \frac{100}{\zeta(2)} \approx 60.7927101\ldots, $$

which is not far from the actual value of $61$.

$\endgroup$ $\begingroup$

There are 6 integers divisible by 2^2 and 4^2, not 1. You are also not counting when integers are divisible by both 3^2 and 9^2, or 2^2, 4^2, and 8^2 for example. The other methods provided are easier to calculate, but your approach is correct except for these errors.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy