# 2015 AIME #3: Where did I go wrong?

This is a question conerning 2015 AIME #3. The problem goes as follows:

1. There is a prime number $p$ such that $\displaystyle 16p+1$ is the cube of a positive integer. Find $p$.

Here is my current working:

By the problem statement:

$16p+1=a^3$

Therefore,

$16p+1 ≡ a^3 \mod 3$

And by Fermat's Little Theorem and the transitive property,

$16p+1 ≡ a \mod 3$

This can be re-arranged by subtracting $1 \mod 3$ from both sides.

$16p ≡ a-1 \mod 3$

The modular multiplicative inverse of $16$ is $1\mod 3$ because:

$x≡16^{-1} \mod 3$

$16x ≡ 1 \mod 3$

Which is true for $x={1,4,7,...}$

Multiplying both sides by the inverse $16^{-1} \mod 3$, you get:

$p≡a-1 \mod 3$

Which appears to be incorrect? Any suggestions/hints? Is this just the plain wrong approach to the problem? (It very likely might be)

Hint: Try $a^3-1=(a-1)(a^2+a+1)=(17-1)(17^2+17+1)$.
• You are welcome. The factorization shows there are in fact no other candidates, for $a^2+a+1$ is always odd. The only viable candidate, with $a=17$, might not work. But it does, since $307$ is prime. – André Nicolas Feb 20 '16 at 21:14
• Your calculation mod $3$ was correct, but it does not tell us enough. Yes, it is true that $p$ must be congruent to $a-1$ modulo $3$, but that does not tell use what (if anything) will work for $a$. – André Nicolas Feb 20 '16 at 21:19
Since $16p+1=a^3$, thus $$16p=(a-1)(a^2+a+1)$$ Now if $p>2$, then it divides only one of $(a-1)$ or $(a^2+a+1)$ (think why?) and $a$ must be odd (why?).
• If $a$ were even, then the RHS would be odd which conflicts with the fact that the LHS is even, so it must be odd. If $p$ divided both then it couldn't be prime. Sounds good. Along with André Nicolas' answer this solves my problem, thanks! – KR136 Feb 20 '16 at 21:12