×

Prime odd problem

Prove that for any integer $$a>2$$, there exists a prime number p such that p divides $$a^3+1$$ but not $$a+1$$.

Note by Lawrence Bush
1 year, 9 months ago

Sort by:

I've managed to reduce down the problem to showing that the solutions of $$a^2-a+1 = 3^k$$ in integers satisfy $$a \le 2$$, but can't proceed anywhere afterwards.

Note that since $$a^3+1 = (a+1)(a^2-a+1)$$, the prime number we're looking for cannot divide $$a+1$$ and hence must divide $$a^2-a+1$$. Thus it suffices to find a prime number $$p$$ that divides $$a^2-a+1$$ but not $$a+1$$.

However, $$\gcd(a^2-a+1, a+1) = \gcd(3, a+1)$$, thus it suffices to find some prime factor $$p$$ of $$a^2-a+1$$ that is not $$3$$. If this is found, $$p$$ cannot divide $$a+1$$, since if it does then $$p$$ divides their GCD, but the GCD is either $$1$$ or $$3$$, impossible to be divisible by $$p$$ whatever it is.

Also note that $$a^2-a+1 > 1$$ for $$a > 2$$, so it suffices to show that $$a^2-a+1$$ is not in the form $$3^k$$ for $$a > 2$$, or in other words the only solutions of $$a^2-a+1 = 3^k$$ in integers satisfy $$a \le 2$$. · 1 year, 9 months ago

Another hint: Use the quadratic formula. · 1 year, 9 months ago

Great! You are 1 step away from a complete solution.

Hopefully that is a sufficient hint (and you shouldn't look down further).

If not,

Hint: If $$\gcd (3, a+1) = 3$$, what does that tell us about $$a$$? Staff · 1 year, 9 months ago

Yes.Corrected it. · 1 year, 9 months ago

Ah. That makes more sense.

I've updated it to "any integer $$a > 2$$" for clarity.

This is an interesting problem. Staff · 1 year, 9 months ago