1
$\begingroup$

Here's the exact wording of the problem:

"The squares, of course, are the numbers 1,4,9,... The square-free numbers are the integers 1,2,3,5,6,... which are not divisible by the square of any prime (so that 1 is both square and square-free). Show that every positive integer is uniquely representable as the product of a square and a square-free number. Show that there are infinitely many square-free numbers."

I was able to prove the first statement with a proof by contradiction, but can't figure out the second part. Does it rely on the first part?

$\endgroup$
  • 12
    $\begingroup$ Hint: all primes are square-free. $\endgroup$ – vadim123 Apr 16 '15 at 1:29
1
$\begingroup$

As @vadim123 notes, all primes are trivially square-free, and there are an infinite number of primes, so this is sufficient for a proof. Of course multiplying together any selection of distinct primes will also give square-free numbers.

In fact, as you might expect, square-free composite numbers are denser than the primes, and also will get ahead of the "square-carrying" numbers. While the proof is several steps beyond my mathematical pay-grade, square-free numbers are about 60% of all numbers, which means that square-free composite numbers will eventually be more the 50% of all numbers (as the proportion of primes diminishes). This actually happens around $30400$.

The count of square-free composite numbers pulls ahead of that for square-carrying numbers much earlier, at $214$.

$\endgroup$

Your Answer

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

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