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.