Modular arithmetic

1. Sep 3, 2011

yavanna

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

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

2. Sep 3, 2011

micromass

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

3. Sep 3, 2011

yavanna

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

4. Sep 3, 2011

micromass

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

5. Sep 3, 2011

I like Serena

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

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).