Skip to main content
Add paragraph about $x^2-Dy^2=1$ and roots of unity
Source Link
Noam D. Elkies
  • 79.9k
  • 15
  • 281
  • 376

The count is $2$ and $6$ for $p=2$ and $p=3$ respectively, and otherwise $p-1$ or $p+1$ according as $p$ is $1$ or $-1 \bmod 3$.

More generally, it is well-known that a smooth plane conic over ${\bf Z} / p {\bf Z}$ has $p+1$ points in the projective plane, so we need only subtract the number of points at infinity, which here is the number of square roots of $-3 \bmod p$. (The primes $p=2,3$ are special because $x^2+3y^2-1$ factors as $(x+y-1)^2 \bmod 2$ and $(x+1)(x-1) \bmod 3$.)

For general $x^2 - D y^2 = 1 \bmod p$ (with $p \not\mid 2D$) the count is $p - (D/p)$ where $(D/p)$ is the Legendre symbol. For $D=-3$ we can also choose between $p-1$ and $p+1$ by observing that the solutions come in triples $\{ (x,y), \frac12(-x-3y,x-y), \frac12(-x+3y,-x-y) \}$ so the count must be a multiple of $3$. This trick is possible here because $(-1+\sqrt{-3})/2$ is a cube root of unity; likewise for $D = -1$ there's a fourth root of unity $\sqrt{-1}$, and the solutions come in quadruples $\{(\pm x, \pm y), (\pm y, \mp x)\}$ so for any odd prime $p$ the number of solutions of $x^2 + y^2 \equiv 1 \bmod p$ is whichever of $p \pm 1$ is a multiple of $4$.

The count is $2$ and $6$ for $p=2$ and $p=3$ respectively, and otherwise $p-1$ or $p+1$ according as $p$ is $1$ or $-1 \bmod 3$.

More generally, it is well-known that a smooth plane conic over ${\bf Z} / p {\bf Z}$ has $p+1$ points in the projective plane, so we need only subtract the number of points at infinity, which here is the number of square roots of $-3 \bmod p$. (The primes $p=2,3$ are special because $x^2+3y^2-1$ factors as $(x+y-1)^2 \bmod 2$ and $(x+1)(x-1) \bmod 3$.)

The count is $2$ and $6$ for $p=2$ and $p=3$ respectively, and otherwise $p-1$ or $p+1$ according as $p$ is $1$ or $-1 \bmod 3$.

More generally, it is well-known that a smooth plane conic over ${\bf Z} / p {\bf Z}$ has $p+1$ points in the projective plane, so we need only subtract the number of points at infinity, which here is the number of square roots of $-3 \bmod p$. (The primes $p=2,3$ are special because $x^2+3y^2-1$ factors as $(x+y-1)^2 \bmod 2$ and $(x+1)(x-1) \bmod 3$.)

For general $x^2 - D y^2 = 1 \bmod p$ (with $p \not\mid 2D$) the count is $p - (D/p)$ where $(D/p)$ is the Legendre symbol. For $D=-3$ we can also choose between $p-1$ and $p+1$ by observing that the solutions come in triples $\{ (x,y), \frac12(-x-3y,x-y), \frac12(-x+3y,-x-y) \}$ so the count must be a multiple of $3$. This trick is possible here because $(-1+\sqrt{-3})/2$ is a cube root of unity; likewise for $D = -1$ there's a fourth root of unity $\sqrt{-1}$, and the solutions come in quadruples $\{(\pm x, \pm y), (\pm y, \mp x)\}$ so for any odd prime $p$ the number of solutions of $x^2 + y^2 \equiv 1 \bmod p$ is whichever of $p \pm 1$ is a multiple of $4$.

Source Link
Noam D. Elkies
  • 79.9k
  • 15
  • 281
  • 376

The count is $2$ and $6$ for $p=2$ and $p=3$ respectively, and otherwise $p-1$ or $p+1$ according as $p$ is $1$ or $-1 \bmod 3$.

More generally, it is well-known that a smooth plane conic over ${\bf Z} / p {\bf Z}$ has $p+1$ points in the projective plane, so we need only subtract the number of points at infinity, which here is the number of square roots of $-3 \bmod p$. (The primes $p=2,3$ are special because $x^2+3y^2-1$ factors as $(x+y-1)^2 \bmod 2$ and $(x+1)(x-1) \bmod 3$.)