## Elementary evaluation of Legendre symbol (3|p)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

### Elementary evaluation of Legendre symbol (3|p)

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

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

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

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).

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

Huh...