1
$\begingroup$

This is from an answer by Robert to this question When are $n!+1$ and $(n+2)!+1$ coprime?

"The roots of $x^2 + 3x + 1$ are $(-3 \pm \sqrt{5})/2$, so $5$ must be a square mod $p$, which says (if $p > 5$) $p \equiv 1$ or $4 \mod 5$."

Can anyone elaborate on how this is derived or point me somewhere where I can read up on it. Thanks.

$\endgroup$
1
  • $\begingroup$ There are three assertions in a row in that quote; which one is the "this" you want information on? $\endgroup$ Dec 24, 2023 at 2:41

1 Answer 1

1
$\begingroup$

the discriminant of the binary quadratic form $u^2 + 3uv + v^2$ is $9-4=5$

If we have (positive) prime $q$ with Legendre symbol $(5|q) = -1$ and $q | u^2 + 3uv + v^2, \; \; $ then both $q | u$ and $q | v.$ Thus, no such prime $q$ can divide any $x^2 + 3x + 1.$ The number $x^2 + 3x + 1$ may be divisible by $5$ and it may be divisible by primes $p \equiv \pm 1 \pmod 5$

background material includes the Legendre symbol and quadratic reciprocity. Here, we used $(q|5) = (5|q) $ because $5 \equiv 1 \pmod 4$

$\endgroup$
1
  • $\begingroup$ same thing. Except for $2$ itself, primes are odd, so $1,4 \pmod 5$ refer to $1,9 \pmod{10}$ $\endgroup$
    – Will Jagy
    Dec 24, 2023 at 3:02

Not the answer you're looking for? Browse other questions tagged .