Prime divisors of the integer $n^2+n-1$ (using the Legendre symbol)

Question

What made me have a question is the following problem.

The prime divisors $p\not=5$ of the integer $n^2+n-1$ are of the form $10k+1$ or $10k+9$.

I thought $\left(\frac 5 p\right) = 1$, because $5 \equiv 1 \pmod 4$.

So $\left(\frac 5 p\right) = (-1)^{p-1}\left(\frac p 5\right)=1$ by qudratic reciprocity.

Then $p$ should be of the form $2k+1$

But I think there is something wrong, and I have lost.

Is there someone to help me?

If $p$ divides $n^2+n-1$, it also divides $4(n^2+n-1)$. Try to see how that relates to $5$. — Daniel Fischer, Nov 19 '13 at 11:29
Do you mean $(2n+1)^2\equiv 5\pmod p$? If yes, I knew already. But I can't go further. — jakeoung, Nov 19 '13 at 11:32
Okay, so you know $\left(\frac5p\right) = 1$. Have you heard of quadratic reciprocity? — Daniel Fischer, Nov 19 '13 at 11:33
Yes. As I mentioned above, I tried to use $\left( \frac 5 p\right)$. I edited my post because of typing error. — jakeoung, Nov 19 '13 at 11:34
"Then $p$ should be of the form $2k+1$." Well, yes, but every prime (except $p=2$) is of the form $2k+1$. And quadratic reciprocity says $(5\mid p)=(p\mid5)$. — Gerry Myerson, Nov 19 '13 at 12:03

score 1 · Accepted Answer · answered Nov 19 '13 at 12:05

1

$n^2+n-1$ is odd, so all its prime factors are odd. You have found that if $p\mid n^2+n-1$, then $(2n+1)^2 \equiv 5 \pmod{p}$, and so for $p\neq 5$ you have $\left(\frac5p\right) = 1$. Quadratic reciprocity then yields $\left(\frac{p}{5}\right) = 1$, since $5 \equiv 1\pmod{4}$. So $p$ is a quadratic residue modulo $5$, and that means $p \equiv\: ? \pmod{5}$?

answered Nov 19 '13 at 12:05

Daniel Fischer

206,697

Thanks to your answer (especially last sentence), I understand it. Thank you. – jakeoung Nov 19 '13 at 12:15

Prime divisors of the integer $n^2+n-1$ (using the Legendre symbol)

1 Answers1

Linked

Related