1
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

Hint: Try $a^3-1=(a-1)(a^2+a+1)=(17-1)(17^2+17+1)$.

$\endgroup$
  • $\begingroup$ Right, that's perfect and so much easier. I had originally tried factoring the cubic, but I think I made a stupid sign error that messed up the result. Thanks! $\endgroup$ – KR136 Feb 20 '16 at 21:10
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Feb 20 '16 at 21:14
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Feb 20 '16 at 21:19
  • $\begingroup$ That's what I suspected. It seemed like I had lost some information/value as I kept reducing the modular equation. I am glad to hear, at the very least, that it was correct even if pointless. $\endgroup$ – KR136 Feb 20 '16 at 21:21
1
$\begingroup$

hint:

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?).

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – KR136 Feb 20 '16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.