# Proof of Euler's Theorem

## Homework Statement

If the divisor P is a prime of the form 4q+1 then the number -1 or P-1 is certainly a residue.

## The Attempt at a Solution

First the book told me to prove that 1 and -1 are the only two remainders that are their own reciprocals modP.

Next, I'm not really sure what to do though.

I know that there has to be P-1/2 quadratic residues meaning 4q+1-1/2= 2q residues, which is an even number.

I suppose next I would assume that -1 is NOT a quad residue modP so that i could prove by contradiction.

Listing the quad residues modp as x1, x2....xp-1/2

That would mean that the product of -1 and x1..... xp-1/2 would yield the quadratic non-residues modP.

However, I really don't know where to go from here, the book says to match the residues with the reciprocals, but I really don't know what to do..

any help would be great!!!

It may just be because I haven't done any number theory in a while, but I don't understand your question. You are saying that P is a prime of the form $P = 4q + 1$ for some $q \in \mathbb N$.

You say that you want to show that -1 or P-1 must be a residue. With respect to what modulo? Maybe this is obvious, but I personally don't understand what you're trying to say.

Edit: Do you mean a quadratic residue?

I am trying to show that -1 or P-1 is a quadratic residue modP

sorry I am using exact language from Euler's work- which is a bit outdated.

Okay, that makes sense.

Sorry for being ignorant, but what "Euler's Theorem" are you trying to prove (there are just so many!). Is it Euler's criterion that states

$$\left( \frac ap \right) \equiv a^{\frac{p-1}2} \mod p$$
where
$$\left( \frac ap \right) = \begin{cases} 1 & a \text{ is a quad. residue of } p \\ -1 & a \text{ is a non-quad. residue of } p \\ 0 & \text{ if } p\mid a \end{cases}$$
is the Legendre symbol?

Also, do you mean to ask "show that -1 (equivalently p-1) is a..." or that there are two cases "-1" and "p-1." Because both are congruent mod p, so I assume you mean the first sentence.

I know I'm asking a lot of questions but I'm trying (part-time) to figure out how to help you.

Yes, I am aware that -1 and P-1 are the same in modP.

Thanks for trying to help, but I figured it out on my own!