1
$\begingroup$

How can I calculate $a^{(P-1)/2}\pmod{P}$?

for example $3^{500001}\bmod{1000003}$ given that $1000003$ is prime.

I know that if we square the number $3^{500001}$ the result will be either $1$ or $-1$ modulo $1000003$.

but my question is how to continue?

I have this question as bonus in previous exam.

2 Answers 2