For any integer , let and let be any prime.

I can show that , however I'm struggling to answer the rest of the qestion:

1) Using Euler’s criterion show that mod p. It looks like we have to show = 1, but how can we show this?

2) Deduce that for some and use this to verfiy that is prime.