Proving Euler's Theorem for Prime Divisors of the Form 4q+1

  • Thread starter Thread starter dancergirlie
  • Start date Start date
  • Tags Tags
    Proof Theorem
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
5 replies · 4K views
dancergirlie
Messages
194
Reaction score
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!
 
Physics news on Phys.org

Discussion

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

[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 \\<br /> -1 & a \text{ is a non-quad. residue of } p \\<br /> 0 & \text{ if } p\mid a \end{cases}[/tex]
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!