Talk:Euler's criterion

From Wikipedia, the free encyclopedia

I think the example could be improved: right now it doesn't illustrate the criterion. We should start with some number a, show that it is a quadratic residue because it can be written as a square, and then compute its (p-1)/2 power to show that the result is 1. Then use a nonresidue and show that you get -1. AxelBoldt 03:07 Oct 16, 2002 (UTC)

Keep in mind that this particular example took me 4-5 hours to complete it right. The example for a=17 first of all tries to show how we can figure it out which numbers are squares modulo a prime without using Euler's criterion for some small a. Then we can watch:

k² ≡ 17 (mod p).

We get all p which solves it {2,4,8,16}. Now using Euler's criterion we see that:

17^(p-1)/2 ≡ 1 mod p; ,

for all p from {2,4,8,16}. We can also see that the latter is true for all p from {9,13,19,43,59,...}. --XJamRastafire 10:50 Oct 16, 2002 (UTC)

The second part of "Proof of Euler's criterion" is not complete. It shows that if a is not a q.r. modulo p then a^((p-1)/2) is not 1, but it doesn't prove that it is -1.

I have made a major cleansweep of this article. The first section really needed attention because the line of reasoning was somewhat unclear - this seems to be the case for most proofs of this criterion found on the net....most of them just cites Fermats little theorem like it was some magic wand. I hope the line of reasoning has become clear now. Holretz