2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ And I guess the natural-numbers tag gets automatically changed to elementary-number-theory? $\endgroup$
    – Vale132
    Aug 15, 2016 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, 2016 at 0:15

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It would be cool to show this without (explicitly) invoking prime decompositions, though. $\endgroup$
    – Arthur
    Aug 15, 2016 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, 2016 at 0:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .