×

# 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
2 years, 9 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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$$.

- 2 years, 9 months ago

Another hint: Use the quadratic formula.

- 2 years, 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 - 2 years, 9 months ago

Yes.Corrected it.

- 2 years, 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 - 2 years, 9 months ago