# Find all prime numbers $p$ such that $16p+1$ is a perfect cube

What I have attempted:

Suppose $16p+1=k^3$ where $k \in Z$ then $16p=k^3-1=(k-1)(k^2+k+1)$ so we can say that $k=17$ and thus $p=17^3+17+1=4931$ which is prime.

How would I find the remaining numbers?

• observe that $k^2+k+1$ is always odd. – Frieder Jäckel Dec 3 '17 at 1:18
• I believe you mean $p=17^{\color{#C00}{2}}+17+1=307$ – robjohn Dec 3 '17 at 2:35

Since $k^3\equiv1\pmod{16}\implies k\equiv1\pmod{16}$, if $16p+1$ is a perfect cube, we must have \begin{align} 16p+1 &=(16k+1)^3\\ &=4096k^3+3\cdot256k^2+3\cdot16k+1 \end{align} Thus, we get $p=256k^3+48k^2+3k=(256k^2+48k+3)k$, which can only be prime if $k=1$, that is $p=307$ and thus $$17^3=16\cdot307+1$$ is the only case.
You had $$16p=k^3-1=(k-1)(k^2+k+1)$$
Because $k$ is odd, $k-1$ is even and $k^2+k+1$ is odd. If $k^2+k+1$ is odd, then $k-1$ must be a multiple of $16$. But for $k-1$ to be a multiple of $16$ other than $16$, $p$ would have to not be a prime. Therefore, $k-1 = 16$ and $k = 17$.
That means that $k^2+k+1$ must be our prime. So plug in $k=17$ to get $$p = 17^2 + 17 + 1 = 307$$
Since $k^2+k+1$ is always odd it is necessary that $16|k-1$.