# Greatest common divisors and modular arithmetic.

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}$.
• You are welcome. There are other ways to prove that if $\gcd(a,b)=1$ then there exist integers $x$ and $y$ such that $ax+by=1$. One way is to run the Euclidean Algorithm and then calculate backwards to find $x$ and $y$. There are several other proofs. – André Nicolas Sep 17 '15 at 18:18