Let $p$ be a prime number. If there's a natural number $k$ so that $k^3+pk^2$ is a perfect cube, prove that $3\mid p-1$ 
Let $p$ be a prime number. If there's a natural number $k$ so that $k^3+pk^2$ is a perfect cube, prove that $3\mid p-1$.

I found this problem in one of my school's selection contests last year. I thought it looked interesting so I gave it a go. I've yet to make any significant progress. I know that $p \equiv 1\ (\textrm{mod}\ 3)$ and I've tried solving for cases where $k \equiv 0,1,2\ (\textrm{mod}\ 3)$, but this seems impossible so I think I have the wrong idea. I've also tried placing $k^3+pk^2$ between two cubes and solving from there, but this also seems wrong. If anyone can guide me on the right path I'd greatly appreciate it. Thanks in advance.
 A: Suppose $k$ is a positive integer and $p$ is a prime such that $k^3+pk^2$ is a perfect cube.

Consider two cases . . .

Case $(1)$:$\;p{\,\mid\,}k$.

Write $k=p^nj$ with $n\ge 1$ and $\gcd(j,p)=1$.

Then we have
$$
k^3+pk^2
=
p^{2n+1}j^2(p^{n-1}j+1)
$$
hence, noting that the factor $j^2$ is relatively prime to each of the factors
$$
p^{2n+1},\;\;\;p^{n-1}j+1
$$
it follows that $j^2$ must be a perfect cube.

Since $j^2$ is a perfect cube, so is $j$.

Claim $n\equiv 1\;(\text{mod}\;3)$.

We can assume $n > 1$, since for $n=1$, the claim is automatic.

Then in the factorization
$$
k^3+pk^2
=
p^{2n+1}j^2(p^{n-1}j+1)
$$
the factor $p^{2n+1}$ is relatively prime to each of the factors
$$
j^2,\;\;\;p^{n-1}j+1
$$
hence $p^{2n+1}$ must be a perfect cube, so $n\equiv 1\;(\text{mod}\;3)$, as claimed.

It follows that $p^{n-1}j$ is a perfect cube, equal to $x^3$ say, for some $x\ge 1$.

But then
$$
p^{n-1}j+1=x^3+1
$$
is strictly between $x^3$ and $(x+1)^3$, so can't be a perfect cube.

Thus case $(1)$ is impossible.

Case $(2)$:$\;p{\,\not\mid\,}k$.

Then we have
$$
k^3+pk^2
=
k^2(k+p)
$$
hence, noting that the factors
$$
k^2,\;\;\;k+p
$$
are relatively prime, it follows that they must both be perfect cubes.

Since $k^2$ is a perfect cube, so is $k$.

Thus $k=x^3$ and $k+p=y^3$ for some $x,y\ge 1$, so we get
$$
p=y^3-x^3=(y-x)(y^2+xy+x^2)
$$
hence since $p$ is prime, we must have $y-x=1$.

Then we get
$$
p=y^3-x^3=(x+1)^3-x^3=3x^2+3x+1
$$
hence $p\equiv 1\;(\text{mod}\;3)$, as was to be shown.
A: You have $$k^3+pk^2 = k^2(k+p) = t^3$$ for some integer $t$.
We can write:
$$k=a^3b^2c$$
where $a^3$ is the maximal cubic factor of $k$, $b^2$ is the maximal square factor of $\dfrac{k}{a^3}$, and $c = \dfrac{k}{a^3b^2}$.
Thus, $k^2(k+p) = a^6b^4c^2(k+p) \Longrightarrow k+p = a^3b^2c+p = b^2cd^3$ for some integer $d$. This implies $b^2c|p$. Either $b^2c=1$ or $b^2c = p$.
Note: I am being fast and loose here. The full argument involves how $a,b,c$ were chosen such that $b$ is cube-free and $c$ is both cube-free and square-free, forcing $b^2c|(k+p)$ to ensure cubic factors.
If $b^2c=1$, then $a^6(a^3+p) = t^3 = a^6d^3 \Longrightarrow a^3+p = d^3$.
Then, $p=(d-a)(d^2+ad+a^2) \Longrightarrow d-a=1, d^2+ad+a^2=p$ or $d-a=p, d^2+ad+a^2=1$. The latter is impossible for any $a,d \in \mathbb{N}$. Therefore, $(a+1)^2+a(a+1)+a^2 = 3a^2+3a+1 = p$. And so, $p-1 = 3(a^2+a)$.
If $b^2c=p$, then we can write $k=a^3p$, which gives:
$$a^6p^2(a^3p+p) = a^6p^3(a^3+1) = t^3$$
This implies $a^3+1$ is a cubic factor of $t^3$, which implies $a=0$, a contradiction to $k$ being a natural number.
