Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Show by a sieve argument that the number of square free integers not exceeding $x$ is less than $$x\prod_p\left(1-\frac{1}{p^2}\right)+o(x),$$where the product extends over all primes.

I happened to see this exercise this morning, and still fail to prove it. Could you give me a proof?

share|cite|improve this question
Do you mean "sum" in "where the product extends"? – Dimitrije Kostic Dec 8 '11 at 2:42
@DimitrijeKostic Sorry, it should be product. – Kou Dec 8 '11 at 2:51
@AndréNicolas Sorry, you are right. – Kou Dec 8 '11 at 2:52

Rough sketch: Have you seen the Wikipedia section on the distribution of squarefree integers? It essentially gives your solution. All you need to notice is that for large $n$, the "probability" that an integer has $p^2$ as a factor is $\frac{p^2-1}{p^2} = \left( 1 - \frac{1}{p^2}\right)$. Since the probability that $n$ has $p^2$ as a factor is roughly independent of the fact it has $q^2$ where $p$ and $q$ are distinct primes, this implies that

$$ \frac{Q(x)}{x} \approx \prod_p \left( 1 - \frac{1}{p^2} \right). $$

I will leave it to you to make this precise.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.