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"?

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

  • $\begingroup$ It would be cool to show this without (explicitly) invoking prime decompositions, though. $\endgroup$ – Arthur Aug 15 '16 at 0:06
  • $\begingroup$ Yeah, the weird thing is that this question appears in an "Intro to Proofs" book that barely touched on the Fundamental Theorem of Arithmetic, so maybe there's a simpler way, but your answer is good to know. $\endgroup$ – Vale132 Aug 15 '16 at 0:20

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.