I have difficulties thinking the relationship between inverse of a number and gcd.
If I want to know if a specific
number module n has an inverse I check if gcd between the number and the module is 1, why?
a≡b(n) has inverse only if gcd(a,n)=1
I know that the result of
gcd(a,n) is the rest of Euclidean division, why does it prove that
a has an inverse