Cubes differences and primality In an exercise (Project Euler 131, not to mention it), we are looking for perfect cubes of the form $n^3 + n^2 p$, where p is prime.
I finally got the answer by trial and error but I don't understand why this implies that n and n+p must be perfect cubes. Any proof ?
UPDATE : following up on @miracle173 answer, can it be proved that p doesn't divide n ?
 A: We have
$$n^2(n+p)=m^3 \tag{1}$$
1) First let us assume that $p$ does not divide $n$.
1.1) Let $q$ be a prime that divides $n$. We have $\gcd(q,p)=1$ and therefore $\gcd(n+p,q)=1$. If $q^e$ is the highest power of $q$ that divides $n$ then $q^{2e}$ is the highest power of $q$ that divides $m^3$. So $3 \mid e$. This holds for all primes dividing $n$  therefore $n$ is a cube.
1.2) If $q$ is a prime that divides $n+p$ (but not $n$) then if $q^e$ is the highest power of $q$ ($\ne p$)  that divides $n+p$ then $q^e$ is the highest power of $q$ that divides $m^3$ and again we have $3 \mid e$. So $n+p$ is a prime , too.
2.) Now we assume that $p$ divides  $n$ and therefore divides  $n+p$, too.
So 
$$n=p^ka \tag{2}$$
for some $a$ and $\gcd(a,p)=1$. We substitute $(2)$ in $(1)$ and get
$$p^{2k+1}a^2(ap^{k-1}+1)=m^3 \tag{3}$$
Because $a$ is relatively prime to the both other factors on the lhs of $(3)$ we can conclude that a is relatively prime to the integer $\frac{m^3}{a^2}$ and so $a^2$ is a cube. Therefore $a$ and $\frac{m^3}{a^2}$ are cubes, too, and (3) can be reduced to 
$$p^{2k+1}(ap^{k-1}+1)=s^3 \tag{4}$$
if we set $s=\frac{m^3}{a^2}$.
If $k>1$ then then $\gcd(p^{2k+1},ap^{k-1}+1)=1$ and so $p^{2k+1} \mid s^3$. 
If $({2k+1}) \not\mid 3$ this is a contradiction, if $({2k+1}) \mid 3$ then $(4)$ reduces to
$$b^3+1=u^3 \tag{5}$$
with $u=\frac{s^3}{p^{2k+1}}$ and $b=a^{\frac{1}{3}} p^{\frac{k-1}{3}}$. Remember that $a$ is a power of 3 and
 $$0 \equiv 2k+1 \equiv k-1\pmod{3}$$
If $k=1$ we get the same equation from $(4)$ But $(5)$ is only valid for $b=0, u=1$.
A: All natural numbers can be decomposed into products of prime powers.  let $n=p_1^{k_1}...p_m^{k_m}$.  Then
$$n^3+n^2\cdot p=p_1^{3k_1}...p_m^{3k_m}+p_1^{2k_1}...p_i^{2k_i+1}...p_m^{2k_m}\cdot$$
$$n^2(n+p)=p_1^{2k_1}...p_m^{2k_m}(p_1^{k_1}...p_m^{k_m}+p_i) $$
The second factor is a natural number and can be also expressed as a product of prime powers.  So let 
$$p_1^{k_1}...p_m^{k_m}+p_i=p_1^{l_1}...p_m^{l_m}$$
Then
$$n^2(n+p)=p_1^{2k_1}...p_m^{2k_m}(p_1^{l_1}...p_m^{l_m})=p_1^{j_1}...p_m^{j_m}=x^3=(yz)^3=y^3z^3$$
So $y^3=p_1^{3i_1}...p_m^{3i_m}=p_1^{2k_1}...p_m^{2k_m}$.  Therefore $3i=2k$ and thus $i=\frac{2k}{3}$.  $\frac{2k}{3}$ is only an integer when $k$ is a multiple of 3.  We use the same argument for $z^3=p_1^{3h_1}...p_m^{3h_m}=p_1^{l_1}...p_m^{l_m}$ and it is more clear in this scenario.
