Elementary evaluation of Legendre symbol (3|p)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Elementary evaluation of Legendre symbol (3|p)

Postby LucasBrown » Tue Jan 05, 2016 3:43 am UTC

Using Euler's criterion and quadratic reciprocity, it can be shown with little difficulty that for odd primes p≥5, we have 3(p-1)/2≡(-1)⌊(p+1)/6⌋ (mod p), which then reduces further to +1 if p≡±1 (mod 12) and -1 if p≡±5 (mod 12).

I'd like to prove this in a more elementary fashion — i.e., I'd like to avoid invoking Euler's criterion and quadratic reciprocity. How would you lot recommend I do this? I'm guessing that some version of this argument will work if I use cube roots of unity instead of ±1, but the necessary changes are currently eluding me.

Context:
Spoiler:
I'm writing some lecture notes for a class to be presented to the San Diego Math Circle on the Lucas-Lehmer test. At one point in the proof (see line (1) on page 9 of the attached PDF), we need to reduce 2(p-1)/2 and 3(p-1)/2 modulo p. As I mentioned earlier, this could be done fairly easily via Euler's criterion and quadratic reciprocity; however, the majority of the students will likely be unfamiliar with this, so I'd rather not bring along all the baggage associated with the general case and instead focus on the particular cases relevant to the proof; presumably, this will permit a simpler argument.
lucaslehmer.pdf
LLT draft
(252.99 KiB) Downloaded 106 times

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Elementary evaluation of Legendre symbol (3|p)

Postby Nitrodon » Tue Jan 05, 2016 8:01 pm UTC

The same argument will work for a=3 (or any a for that matter).

Spoiler:
I'm not confident in my ability to write clearly, so I'll just demonstrate for p=17.

388! = (3)(6)(9)(12)(15)(18)(21)(24) ≡ (3)(6)(-8)(-5)(-2)(1)(4)(7) ≡ (-1)38! (mod 17), so 38 ≡ -1 (mod 17).

The RHS is always a rearrangement of 1, 2, 3, ..., (p-1)/2 up to sign, since if we have any repeats, it follows that a(k1 ± k2) ≡ 0 (mod p).

User avatar
LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Re: Elementary evaluation of Legendre symbol (3|p)

Postby LucasBrown » Wed Jan 06, 2016 1:57 am UTC

Huh...

Thanks, that was helpful.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests