/sci/ - Science & Math

i am best tripfag

The solutions of <span class="math">x^2=y^2+1[/spoiler] are given by <span class="math">x=\frac{r+r^{-1}}{2}, y = \frac{r-r^{-1}}{2}, r \in \mathbb{F}_p^*[/spoiler].

Two numbers <span class="math">r,s \in \mathbb{F}_p^{*} [/spoiler] give the same value of <span class="math">x^2[/spoiler] iff <span class="math">\left(\frac{r+r^{-1}}{2}\right)^2 = \left(\frac{s+s^{-1}}{2}\right)^2[/spoiler] iff <span class="math">r^2+r^{-2} = s^2+s^{-2} (=4x^2-1)[/spoiler]. But then <span class="math">\{r^2, r^{-2}\}[/spoiler] and <span class="math">\{s^2, s^{-2}\}[/spoiler] are both the set of roots of <span class="math">t^2-(4x^2-1)t+1[/spoiler], so <span class="math">\{r^2, r^{-2}\} = \{s^2, s^{-2}\}[/spoiler]. The number we want is the number of distinct sets <span class="math">\{r^2, r^{-2}\}, r \in \mathbb{F}_p^*[/spoiler]

<span class="math">1[/spoiler] and <span class="math">-1[/spoiler] are the only numbers which are their own inverses, and <span class="math">1[/spoiler] is always a residue. If <span class="math">-1[/spoiler] is not a residue, i.e. <span class="math">p \equiv 3 \pmod 4[/spoiler], the total is one plus half the number of remaining residues, or <span class="math">1 + \frac{1}{2}\left(\frac{p-1}{2}-1\right) = \frac{p+1}{4}[/spoiler].

OTOH if <span class="math">-1[/spoiler] is a residue so <span class="math">p \equiv 1 \pmod 4[/spoiler], the total is <span class="math">2 + \frac{1}{2}\left(\frac{p-1}{2}-2\right) = \frac{p+3}{4}[/spoiler]