2
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer Sep 20 '13 at 14:49
  • $\begingroup$ @DanielFischer But since $n^4\equiv -1$ it can't be $1,2,4$... $\endgroup$ – Thomas Andrews Sep 20 '13 at 14:52
2
$\begingroup$

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.
| cite | improve this answer | | | | |
$\endgroup$
3
$\begingroup$

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

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

| cite | improve this answer | | | | |
$\endgroup$
  • 2
    $\begingroup$ I still cannot proceed. Can guide me further? $\endgroup$ – Idonknow Sep 21 '13 at 15:04

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.