# Show that the odd prime divisors of the integer $n^2+n+1$ which are different from $3$ are of the form $6k+1$.

1)The odd prime divisors of the integer $n^4+1$ are of the form $8k+1$.

My attempt: Let $p$ be odd divisor of $n^4+1$.Then $n^4+1 \equiv 0$ (mod p) $\Rightarrow n^4 \equiv -1$ (mod p) $\Rightarrow n^8 \equiv 1$ (mod p). Hence, the order of $n$ modulo $p$ is 8, which implies that $8 | \phi(p)=p-1 \Rightarrow p=8k+1$

The part i not sure is the order of $n$ modulo $p$. How do I show the order of $n$ modulo $p$ is 8?

2)Show that the odd prime divisors of the integer $n^2+n+1$ which are different from $3$ are of the form $6k+1$.

My attempt: Let $p$ be odd divisor of $n^2+n+1$. Then $n^2+n+1 \equiv 0$(mod p). I try to mimick the method above but i fail.

Can anyone guide me?

• Ad 1), you know $n^8 \equiv 1 \pmod{p}$, so the order is a divisor of $8$. But $n^4 \not\equiv 1 \pmod{p}$, so the order cannot be $4,2$, or $1$. Ad 2) $n^3 - 1 = (n-1)(n^2+n+1)$, so $n^3 \equiv 1 \pmod{p}$. Then you can have $n \equiv 1 \pmod{p}$, or the order of $n$ modulo $p$ is $3$. – Daniel Fischer Sep 20 '13 at 14:49
• @DanielFischer But since $n^4\equiv -1$ it can't be $1,2,4$... – Thomas Andrews Sep 20 '13 at 14:52

Problem 1. We are facing the situation $n^4 \equiv -1$ (mod $p$) which implies $n^8 \equiv 1$ (mod $p$).

The order of $n$ modulo $p$ (that I denote as $\operatorname{ord}_p(n)$) is a divisor of $8$ namely $\operatorname{ord}_p(n) \in \{\, 1,2,4,8 \, \}$. However $(a^1)^4 = (a^2)^2 = a^4 \not\equiv 1$ (mod $p$) so it forces $\operatorname{ord}_p(n) = 8$. Then you are well aware that $8 \mid \phi(p)=p-1$ implies $p=8k+1,\ k \in \mathbb{Z}$.

Problem 2. We are facing the situation $n^2+n+1 \equiv 0$ (mod $p$). Yet let's look at an apparently "weaker" problem by introducing an additional factor $(n-1)(n^2+n+1) = n^3 -1 \equiv 0$ (mod $p$); in other words $n^3 \equiv 1$ (mod $p$).

We see that the order of $n$ modulo $p$ is a divisor of $3$ namely $\operatorname{ord}_p(n) \in \{\, 1,3 \, \}$.

1. Assume $\operatorname{ord}_p(n) = 1$. Then $n \equiv 1$ (mod $p$) and $n^2 + n + 1 \equiv 3$ (mod $p$). Since we want $p$ to be a divisor it must be the case that $p \mid 3$ but there are no odd primes $p>3$ satisfying this.
2. Assume $\operatorname{ord}_p(n) = 3$. Then $3 \mid \phi(p)=p-1$ implies $p=3k+1,\ k \in \mathbb{Z}$. Excluding odd numbers leaves us with $p=6k+1,\ k \in \mathbb{Z}$. Since this requirement is enforced for a weaker problem, it is necessarily enforced for the original problem as well.

Hint: $$4(n^2+n+1)=(2n+1)^2+3$$

Alternatively: $$(n-1)(n^2+n+1)=n^3-1$$

• I still cannot proceed. Can guide me further? – Idonknow Sep 21 '13 at 15:04