Prove that if p is a prime and a0mod p then there is a uniqu

Prove that, if p is a prime, and a0(mod p) then there is a unique congruence class b such that ab 1(mod p ) ?

I want the answer.by using Euclidean Algorithm.

Solution

Since, a is not 0 mod p. Hence,

gcd(a,p)=1

So by Euclid\'s algorithm there exist:b,y so that:

ab+py=1

Hence, ab=1 mod p

where b,y can vary as:

(b+kp,y-ka)

So, b+kp forms a unique congruence class so that:

ab=1 mod p