logo

Euler's Criterion 📂Number Theory

Euler's Criterion

Theorem 1

Regarding the prime number p2p \ne 2, ap12(ap)(modp) a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p}

Explanation

It means that, to see if aa is a quadratic residue (QR) or a non-quadratic residue (NQR), one could just calculate blindly. Of course, exponentiation is not always an easy task, but it’s better than calculating every number. The proof itself is not too difficult, but because many auxiliary lemmas are used, some prior study is needed for easy understanding.

Proof

Let’s look into the cases where aa is QR and NQR.

Case 1. When aa is QR

Since aa is QR, for some bb, a=b2a = b^2 holds, and the following is true. ap12b2p12bp1(modp) a^{p-1 \over 2} \equiv b^2{p-1 \over 2} \equiv b^{p-1} \pmod{p}

Fermat’s Little Theorem: ap11(modp)a^{p-1} \equiv 1 \pmod{p}

According to Fermat’s Little Theorem, bp11(modp)b^{p-1} \equiv 1 \pmod{p} is true, so ap12(ap)1(modp) a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv 1 \pmod{p}


Case 2. When aa is NQR

Starting with the congruence equation xp110(modp)x^{p-1} - 1 \equiv 0 \pmod{p}.

Fundamental Theorem of Algebra for Congruence Equations: For f(x)=a0xd+a1xd1++ad1x+adf(x)=a_{ 0 }x^{ d }+a_{ 1 }x^{ d-1 }+ \cdots +a_{ d-1 }x+a_{ d }, the equation f(x)0(modp)f(x)\equiv 0 \pmod{p} has at most dd non-congruent solutions

By the Fundamental Theorem of Algebra, the below congruence equation has p1p-1 non-congruent solutions.

0xp11(xp12+1)(xp121)(modp) 0 \equiv x^{p-1} - 1 \equiv (x^{p-1 \over 2} +1) (x^{p-1 \over 2} -1) \pmod{p}

Number of QRs and NQRs: For a prime number larger than 22, pp, there are exactly (p1)2\displaystyle {(p-1) \over 2} QRs and NQRs

Meanwhile, for the prime number pp, there exist exactly p12\displaystyle {p-1 \over 2} QRs and NQRs, and as seen in Case 1, the p12\displaystyle {p-1 \over 2} QRs are solutions to (xp121)0(modp)\displaystyle (x^{p-1 \over 2} -1) \equiv 0 \pmod{p}. Hence, the remaining p12\displaystyle {p-1 \over 2} NQRs must be solutions to (xp12+1)0(modp)(x^{p-1 \over 2} +1) \equiv 0 \pmod{p}. Therefore, the following holds. ap12(ap)1(modp) a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv -1 \pmod{p}


By combining Case 1 and 2, we obtain the following. ap12(ap)(modp) a^{p-1 \over 2} \equiv \left( {a \over p} \right) \pmod{p}


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p150. ↩︎