Euler's Criterion

• March 30th 2010, 10:52 AM
tarheelborn
Euler's Criterion
I am trying to show that x^2 == 25(mod 997) has a solution, but I can't seem to get there.
• March 30th 2010, 11:56 AM
Black
x=5?
• March 30th 2010, 12:00 PM
tarheelborn
Yeah, thanks. Caught onto that after I belatedly realized that 997 is prime. Thank you!
• March 30th 2010, 12:12 PM
Bruno J.
Quote:

Originally Posted by tarheelborn
Yeah, thanks. Caught onto that after I belatedly realized that 997 is prime. Thank you!

It doesn't matter in this case that 997 is prime; you'd still have the solution $x=\pm 5$ (although perhaps you'd have others as well).
• March 30th 2010, 12:50 PM
tarheelborn
But since 997 is prime, wouldn't Lagrange's theorem apply to show that there are ONLY 2 solutions?
• March 30th 2010, 01:51 PM
tonio
Quote:

Originally Posted by tarheelborn
But since 997 is prime, wouldn't Lagrange's theorem apply to show that there are ONLY 2 solutions?

What has Lagrange to do here? Since 997 is a prime there are only two solutions because any polynomial p(x) ( e.g., $x^2-25=0$ ) over a field can have at most $\deg(p(x))$ different roots in some extension of the field.

Tonio
• March 30th 2010, 01:57 PM
tarheelborn
Quote:

Originally Posted by Bruno J.
It doesn't matter in this case that 997 is prime; you'd still have the solution $x=\pm 5$ (although perhaps you'd have others as well).

Sure, I see that; I was just trying to clarify your statement that perhaps you would have other solutions as well. Thank you so much for your help!