every non-zero element of Zp is invertible

[Student x]

Hi everyone,
can you please help me proving that:

If p is prime, then every non-zero element of Zp is invertible, I got advised that I might need to use euclid's algorithm to prove that.

 

[HallsofIvy]

Suppose 0< a< p. a is 'invertible' if there exist b, 0< b< p, such that ab= 1 (mod p). And that is true if and only if there exist an integer n such that ab= np+ 1. That is the same as ab- np= 1 where a, b, n, and p are integers. That is where you can use the "Euclidean Algorithm".