I am working on the following question and am unsure how to proceed.
"Let a,n be positive integers and let d = gcd(a,n). Show that the equation ax ≡ 1(n) has a solution iff d = 1."
I know that $a^{\phi(n)} \equiv 1$ (mod n) when (a,n) = 1, by the Euler-Fermat theorem however I am not sure if this is as useful as I think it is. Any help is appreciated.
You are essentially finished, let $x=a^{\varphi(n)-1}$.