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.