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?

  • 1
    $\begingroup$ Try for prime divisors and consider the multiplicative order of $n$ mod $p$. Note that $n^2+n+1$ is odd. $\endgroup$ – 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?

  • $\begingroup$ 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? $\endgroup$ – Mary Star Dec 15 '18 at 21:23
  • 2
    $\begingroup$ @MaryStar Exactly, but what is a product of things $\equiv 1\pmod 3$ congruent to mod 3? $\endgroup$ – Will Fisher Dec 15 '18 at 21:24
  • $\begingroup$ 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? $\endgroup$ – Mary Star Dec 15 '18 at 21:51
  • 2
    $\begingroup$ @MaryStar Yep. And like you said, odd divisors are products of odd primes, all of which we know are congruent to 1 mod 3. $\endgroup$ – Will Fisher Dec 15 '18 at 21:53
  • $\begingroup$ Great!! Thanks a lot!! :-) $\endgroup$ – Mary Star Dec 15 '18 at 21:59

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.