Proof of Euler's Theorem

  • #1
200
0

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.

Homework Equations





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!!!
 

Answers and Replies

  • #2
743
1
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 [itex] P = 4q + 1 [/itex] for some [itex] q \in \mathbb N [/itex].

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?
 
  • #3
200
0
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.
 
  • #4
743
1
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

[tex] \left( \frac ap \right) \equiv a^{\frac{p-1}2} \mod p [/tex]
where
[tex] \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} [/tex]
is the Legendre symbol?
 
  • #5
743
1
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.
 
  • #6
200
0
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!
 

Related Threads on Proof of Euler's Theorem

  • Last Post
Replies
2
Views
5K
Replies
3
Views
8K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
2
Views
3K
Replies
0
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
5
Views
833
Top