# Talk:Euler's criterion

Jump to: navigation, search
Valid proof?::

αi(p−1)/2 ≡ 1 (mod p). By Fermat's little theorem, p − 1 divides i(p − 1)/2

How does this follow?

- —Preceding unsigned comment added by 86.131.60.104 (talk) 21:54, 6 February 2011 (UTC)

I think it follows not from Fermat's little thorem but from the definition of primitive roots: p-1 is the minimum k such that $\alpha^k \equiv 1$, so if $\alpha^k \equiv 1$ k should be a multiple of p-1.222.148.64.59 (talk) 14:34, 2 May 2011 (UTC)

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:
k2 ≡ 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

Cleaned up your 'cleansweep' BlueRaja (talk) 03:57, 14 November 2009 (UTC)

## Jump in math

The very last example makes sense if you already know the criterion, but not if you do not. It claims 38=16. That is not true. 38=6561. Then 6561%17=16. I assume that use of % for mod in this article is not proper. What is the proper format for representing 6561%17 so that users who are attempting to understand the criterion will be able to follow this current missing step? -- kainaw 02:22, 8 March 2009 (UTC)

It was just a typo, it should have read 38 ≡ 16. — Emil J. 13:57, 8 March 2009 (UTC)

## Eulers Criterion

shouldn't this be "Eulers criterion?" —Preceding unsigned comment added by 69.181.220.209 (talk) 21:09, 4 July 2010 (UTC)

No, why? It's a perfectly regular use of a possessive apostrophe.—Emil J. 12:38, 5 July 2010 (UTC)

## Generalized Euler's criterion

We have been taught that the following is called the Generalized Euler's criterion:

Let N > 1 have a primitive root, and a co-prime to N. Then xka (mod N) has a solution iff $a^{\frac{\phi(N)}{\gcd(k, \phi(N))}} \equiv 1 \pmod{N}$.

Now, I don't know whether this is the correct name of the above statement (so I'm not editing the article), but this article mentions neither the statement itself nor contains a reference to a place that does. At least the latter should be done. 08:46, 9 August 2012 (UTC) — Preceding unsigned comment added by Ybungalobill (talkcontribs)

I've never heard it called the generalized Euler's criterion. = Virginia-American (talk) 12:22, 9 August 2012 (UTC)