Euler's Criterion (Part 1)

In this video we look at a proof of Euler's Criterion which gives us a way to determine whether a number is a quadratic residue modulo an odd prime number p.

In this proof we do not use Lagrange's theorem (number theory) that if the leading coefficient of a polynomial f of degree m is not divisible by p, then f =0 mod p has at most m incongruent roots mod p. We proof Euler's Criterion using Lagrange's theorem in the next part.

Time stamps
00:00
01:45 Case 1
02:09 Case 2
03:01 Case 3

At 03:42 we are making use of the fact that since p is a prime therefore Z/pZ is an integral domain (in fact it is a field and it is a field if and only if p is a prime) and so has no nontrivial zero divisors.

In fact, at 05:44, we can in an exactly analogous manner show that if p=mn+1 is a prime number and a^m-1 is divisible by p, then there will always exist x and y, each coprime to p, such that ax^n-y^n is divisible by p. This result and the proof of it are given in Theorem 19 in Euler's paper 'Theoremata circa residua ex divisione potestatum relicta' (which is paper E262 in Eneström index). (In fact we can use a similar proof to show that if p=mn+1 is a prime and we have that a^m=b^m mod p for some unequal a and b, each coprime to p, then we can find x and y each coprime to p such that ax^n=by^n mod p. This question arises in Corollary 2 of Theorem 15 in Euler's paper 'Theoremata circa divisores numerorum', E134)

Hint to prove the result about mth differences at 13:41; use mathematical induction on m assuming the result is true for all positive integers up to m. You can also find an ingenious proof of this result in Articles 10-15 in Euler's paper E241 'Demonstratio Theorematis Fermatiani Omnem Numerum Primum Formae 4n+1 Esse Summam Duorum Quadratorum".