Every odd divisor is $\equiv 1\bmod 3$

If $$n$$ is a positive integer with $$n\equiv 2\pmod 3$$ then I want to show that each odd divisor of $$n^2+n+1$$ is congruent to $$1\pmod 3$$.



I have done the following:

Let $$d$$ be an odd divisor of $$n^2+n+1$$.

Then $$n^2+n+1\equiv 0\bmod d \Rightarrow (n-1)(n^2+n+1)\equiv 0\bmod d \Rightarrow n^3-1\equiv 0 \bmod d \Rightarrow n^3\equiv 1\bmod d$$

Since $$n\equiv 2\pmod 3$$ we have that $$n=2+3k$$. Then $$n^3=(2+3k)^3=27k^3+54k^2+36k+8$$

We have that $$n^3\equiv 1\bmod d$$ therefore we get $$27k^3+54k^2+36k+8\equiv 1\bmod d \Rightarrow 27k^3+54k^2+36k+7\equiv 0\bmod d$$

Is everything correct so far? How could we continue?

• Try for prime divisors and consider the multiplicative order of $n$ mod $p$. Note that $n^2+n+1$ is odd. – Mindlack Dec 15 '18 at 20:57

Hint: Start with odd prime divisors. As you have correctly shown, for any $$p\mid n^2+n+1$$ we have that $$n^3\equiv 1\pmod p.$$ Hence $$\text{ord}_{p}(n)\mid 3$$. Since $$n\equiv 2\not\equiv 1\pmod p$$ we know that $$\text{ord}_{p}(n)=3$$. However, we also know that for every $$m$$ and $$x$$ coprime to $$m$$ that $$\text{ord}_m(x)\mid \phi(m)$$. How can we apply this in this scenario? Once we know the statement holds for every odd prime divisor, what can we say about every odd divisor?
• So, in this case we have that $\text{ord}_p(n)\mid \phi(p)\Rightarrow 3\mid p-1 \Rightarrow p-1=3k \Rightarrow p=3k+1$. That means that $p\equiv 1\pmod 3$. Any odd divisor will be a product of odd prime divisors, right? So we have to show that the product of terms in the form $3m+1$ will be again in that form, right? – Mary Star Dec 15 '18 at 21:23
• @MaryStar Exactly, but what is a product of things $\equiv 1\pmod 3$ congruent to mod 3? – Will Fisher Dec 15 '18 at 21:24
• It is congruent to $1$ modulo $3$, since let $a\equiv b\equiv 1\bmod 3$ then $ab\bmod 3\equiv (a\bmod 3 )(b\bmod 3)\bmod 3\equiv 1\bmod 3$, right? – Mary Star Dec 15 '18 at 21:51