Find all prime numbers $p$ for which the number of ordered pairs of integers $(x, y)$ with $0\leq x, y < p$ satisfying the condition \[y^2 \equiv x^3 - x \pmod p\] is exactly $p.$
Problem
Source: Turkey National Olympiad 2002 - D2 - P1
Tags: modular arithmetic, quadratics, number theory, prime numbers, number theory unsolved
11.03.2011 15:27
I am not sure,but I can't understand where the problem is.Please rescue me if wrong. If $(x,y)$ is a solution,$(x,-y)$ too,so the number of solutions is even,then $p=2$
11.03.2011 15:46
mathmdmb wrote: I am not sure,but I can't understand where the problem is.Please rescue me if wrong. If $(x,y)$ is a solution,$(x,-y)$ too,so the number of solutions is even,then $p=2$ The problem is here! amparvardi wrote: $0 x, y < p$ $0 < x, y < p.$
11.03.2011 16:29
if $(x,y)$ be a solution,then $(x,p-y)$ also is a solution so $p=2$ and this is wrong.so there is not any prime numbers.
11.03.2011 17:26
If it is just mine $(x,y)\to (x,p-y)$ in other words taking $\mod p,(x,p-y)\equiv (x,-y)$ So I am confused
29.12.2011 18:09
If $(x,y)$ is a solution then $(x, -y) \, \mod \, p$ is also solution, but there may happen that $y=0$, so it doesn't follow that the number of solutions is even. $y=0$ exactly when $x= 0,\, 1,\, -1$, so in remaining $p-3$ residues, exactly half must satisfy the following assertion: (1) $f(x) = x^3 - x$ is quadratic residue modulo $p$. Case 1. $ \frac{p-1}{2}$ is odd. If $a\in \mathbb{Z}_p,\, a \neq 0$ then $(\frac{a}{p}) (\frac{-a}{p}) = (-1)^{\frac{p-1}{2}}= -1$ (here $(\frac{a}{p})$ is the Legendre symbol) => one of $a, -a$ is quadratic residue and the other is not. Because $f(x) = - f(-x)$ then when $x=2,3,\cdots, p-2$ , $f(x)$ will be quadratic residue modulo $p$ for exactly $\frac{p-3}{2}$ values of $x$. Hence the number of solutions will be $2.\frac{p-3}{2} +3 = p$. Case 2. $2/ \frac{p-1}{2}$. If $a \in \mathbb{Z}_p$ then $f(a), \, f(-a)$ are both quadratic residues or both are not. Because the number of couples $(a,\, -a), \, a\in \mathbb{Z}_p,\, a \neq 0, 1, -1 $ is odd, so when $x=2,3,\cdots, p-2$ in more or less(but not equal to) than $\frac{p-3}{2}$ cases $f(x)$ will be quadratic residue modulo p and the number of solutions will not be equal to $p$. Finally, all prime numbers $p$ for which the number of ordered pairs is $p$ can be represented as $p=4k+3$.
26.04.2021 13:02
Observe that $p=2$ is a solution. From now on we suppose that $p>2$. Lemma 1. The number of solutions $(x,y)$ of the equation $x^2=y^3-y$ in $\mathbb{F}_p$ is equal to $p$ if and only if $$\sum_{y\in\mathbb{F}_p}\left(\frac{y^3-y}{p}\right)=0,$$where $\left(\frac{a}{p}\right)$ is the Legendge symbol. Proof Let $a=|\{y\in \mathbb{F}_p: \left(\frac{y^3-y}{p}\right)=1\}|, b=|\{y\in \mathbb{F}_p: \left(\frac{y^3-y}{p}\right)=-1\}|$ and $c=|\{y\in \mathbb{F}_p: \left(\frac{y^3-y}{p}\right)=0\}|$, then $c=3, a+b+3=p$ and $$\sum_{y\in\mathbb{F}_p}\left(\frac{y^3-y}{p}\right)=a-b$$On the other hand, the number of solution of the mentioned equation is equal to $N=2a+3$. Therefore $N=p$ if and only if $a=\frac{p-3}{2},$ which is equivalent to $a=b$, due to the relation $a+b+3=p$. Lemma 2. For a prime $p$ $$S=\sum_{y\in\mathbb{F}_p}\left(\frac{y^3-y}{p}\right)=0,$$if and only if $p\equiv -1(\text{mod}\ 4)$. Proof Let $h=\frac{p-3}{2}$. If $S=0$, then $$P=\prod_{y\in\mathbb{F}_p, y\neq 0,\pm 1}\left(\frac{y^3-y}{p}\right)=(-1)^h$$due to Lemma 1. Notice that if we put $F(x)=\frac{x^{p-1}-1}{x^2-1}=1+x^2+x^4+...+x^{2h}$, then $$\prod_{y\in\mathbb{F}_p, y\neq 0,\pm 1}(y^3-y)=F(0)F(1)F(-1)=(h+1)^2$$and therefore $$(-1)^h=P=\left(\frac{(h+1)^2}{p}\right)=1,$$so that $h$ is even. This precisely means that $p\equiv -1(\text{mod}\ 4)$. Conversely, if $p\equiv -1(\text{mod}\ 4)$, then $$S=\sum_{y\in\mathbb{F}_p}\left(\frac{(-y)^3-(-y)}{p}\right)=\left(\frac{-1}{p}\right)S=-S,$$which gives $S=0$ .
26.04.2021 14:03
Obviously $p=2$ is a solution. Suppose $p$ is odd. If $p \equiv 1 \pmod{4}$, then if $(x,y)$ is a solution, $(x,p-y)$, $(p-x,z)$, $(p-x,p-z)$ are also solutions for some $z \in \mathbb{Z}$ since $-1$ is a quadratic residue modulo $p$. So $x=0,1,p-1$ always give us $3$ solutions. Suppose $(x_1 , y_1) , \dots , (x_{\frac{p-3}{2}} , y_{\frac{p-3}{2}})$ are the other solutions with $1\leq y_i \leq \frac{p-1}{2}$ for all $i$. Since if $x$ produces a solution, $-x$ also produces a solution, we must have that $\frac{p-3}{4} \in \mathbb{Z}$ but that is clearly impossible. So no solution if $p\equiv 1 \pmod{4}$. Assume $p\equiv 3 \pmod{4}$. Now since $-1$ is not a quadratic residue, for $2\leq x \leq p-2$ we know exactly one of $x,p-x$ produces $2$ solutions. So total number of solutions will be $3 + 2\cdot \frac{p-3}{2} = p$. So all the prime numbers which are congruent to $3$ modulo $4$ are solutions.