# Naturals $\leq 10^6$ that are either squares or cubes

Question: How many natural numbers less than or equal to 1 million are either squares or cubes of natural numbers?

My Thoughts: I'm having trouble understanding the "intersection" component. I think that we're trying to determine the number of $k \in \mathbb{N}$, $k \leq 1,000,000$, such that $k = a^2$ and $k=b^3$ for some $a,b \in \mathbb{N}$. But the solutions I've seen simply note that $1,000,000 = 10^6$, so there are 10 naturals $c$ such that $c^6 = (c^2)^3 = (c^3)^2 \leq 10^6$.

I don't see how these definitions of the intersection are compatible. How is "the number of naturals that are both the square of some natural number and the cube of some natural number" the same as "the number of naturals that are the cube of the square of some natural number"?

• And I guess the natural-numbers tag gets automatically changed to elementary-number-theory? – Vale132 Aug 15 '16 at 0:01
• Hint: a number is a perfect $k$th power if and only if the exponents in its prime factorization are multiples of $k$. – symplectomorphic Aug 15 '16 at 0:15

If $c$ is both the square of some natural number and the cube of some (other) natural number, then for every prime factor that divides $c$, that prime must divide $c$ to a power that is even (since $c$ is a square) and at the same time divisible by $3$ (since $c$ is a cube). That means that any such prime must divide $c$ by a power that is divisible by $6$. Therefore, $c$ is the sixth power of some natural number.