Up to here is awsome

but from here we can't really divide by a inSuppose has a solution. Then for some .

but we do have this tells us that gcd(a,n)=1 becuase we have expressed 1 as a linear combination of a and n.

ummm not quite first x=0 is a solutionSuppose . Then and are coprime. So has no solutions. Hence has a solution.

Then by the Euclidean algorithm there exists such that

use this to show that there does exists a solution.