Modular arithmetic

[yavanna]

If p is a prime and a an integer coprime with p, why is

a^{\frac{p-1}{2}}\equiv -1 mod p ?

[micromass]

It's not true. Consider p=5 and a=4.

[yavanna]

Yes, i was trying some examples and I think it only works with primitive roots... But why?

[micromass]

Are you aware of Fermat's little theorem?? Try to use that...

[I like Serena]

Hah, that's basically the definition of a primitive root. :smile:

Any co-prime "a" has a "period" indicating how soon it gets to "1".
Fermat's little theorem guarantees that (p-1) will bring it back to "1".
The actual period will be a divider of (p-1).
Only for primitive roots, the period is exactly (p-1).