C 5

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

w

0 users

TOPICS

No tags match your search

M

No tags match your search

M

C 5

G H J

Reveal topic tags

analytic geometry

Quadratic Residues

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 3 Y

Y by Adventure10, UpvoteFarm, Mango247

Let $p$ be an odd prime and let $Z_{p}$ denote (the field of) integers modulo $p$ . How many elements are in the set $\{x^{2}: x \in Z_{p}\}\cap \{y^{2}+1: y \in Z_{p}\}?$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#2 h May 25, 2007, 12:24 AM • 5 Y

Y by shinichiman, hellomath010118, Adventure10, UpvoteFarm, Mango247

That notation looks ugly, I will use $\mathbb{F}_p$ for the field with $p$ elements

Lets work completely in $\mathbb{F}_p$ .
We look for the solutions $(x,y)$ of $x^2 = y^2+1$ . One is given by $P=(1,0)$ and we use the method of secants to find all:
We intersect lines $y=\lambda (x-1)$ through $P$ with slope $\lambda$ with the hyperbola $x^2-y^2=1$ .
This gives $x^2- (\lambda(x-1))^2=1 \iff (x-1)(x+1) - \lambda^2(x-1)^2 =0$ , having $x=1$ (giving $y=0$ , so resulting in the point $P$ ) as solution. The second solution is that of $(x+1) - \lambda^2(x-1) =0 \iff x=- \frac{1+\lambda^2}{1-\lambda^2}$ .

To $\lambda = \pm 1$ , there corresponds no solution, but all other $\lambda$ give us some $x$ and thus also some $y$ in an unique way.
If $\lambda, \lambda^\prime$ give the same $(x,y)$ , then $\lambda (x-1) = y = \lambda^\prime (x-1)$ , giving $\lambda=\lambda^\prime$ if $x \neq 1$ . If $x=1$ , we have $1=x=- \frac{1+\lambda^2}{1-\lambda^2} \iff 2=0$ , contradiction.

Conversely, every $(x,y) \neq P=(1,0)$ on the hyperbola gives us $\lambda = \frac{y}{x-1}$ by the same arguments. We see that this gives us a bijection between the slopes $\lambda \neq \pm 1$ and the points $\neq P$ on the hyperbola-

Thus the set of points $(x,y)$ on the hyperbola equals $1$ (for $P=(1,0)$ ) plus the number of $\lambda \neq \pm 1$ , thus in total equals $p-1$ .
If $y=0$ , then $x^2=1 \iff x= \pm 1$ , thus there are exactly two points with $y=0$ .
Similar, $x=0$ yields $y^2=-1$ , having only (two) solutions if $p \equiv 1 \mod 4$ .
If $x,y \neq 0$ , there are always exactly four points with the same value of $x^2$ , namely $(\pm x , \pm y)$ .

It's also possible to get this result from http://www.problem-solving.be/pen/viewtopic.php?t=134 .

Counting again, we get $\frac{p-1-4}{4}+1+1=\frac{p+3}{4}$ values for $x^2$ if $p \equiv 1 \mod 4$ and $\frac{p-1-2}{4}+1=\frac{p+1}{4}$ such values for $p \equiv -1 \mod 4$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a