Let $a$ and $n$ be positive integers, and let $d = \gcd(a, n)$. Show that the equation $ax\equiv 1 \pmod{n}$ has a solution for some integer $x$ if and only if $d = 1$".
I know that if $ax\equiv 1 \pmod{n}$, then $ax=nu+1$ giving $1=ax-nu$, meaning $d=1$. However, I'm not sure what to do for proving the other direction. Any help is appreciated.
On
You have solved the 'only if' part. This can be a way to proceed for the 'if' part. Now, we have $d=1$ which means that $\gcd(a,n)=1$. Consider the set $[ai] \bmod n $ for $i$ ranging from $1$ to $n$. If we have: $$ai=aj \pmod n$$ Then $n$ divides $a(i-j)$. As $\gcd(a,n)=1$, $n$ divides $i-j$ and since $i,j$ range from $1$ to $n$, $i=j$. This means that two distinct elements of our set are always different. Since there are $n$ values in the set, and there are $n$ possible remainders, one of them must be $1$ which proves the existence of $i$ for which $ai=1 \pmod n$.
On
From Bezout's identity, we have $ax+bn=1$ if and only if $gcd(a,n)=1$. $ax+bn=1$ same as, $ax\equiv 1\pmod{n}$.
On
(i) If $ax\equiv 1 \pmod{n}$ has a solution, then you can write $ax - bn = 1, b\in\mathbb{Z}$. No prime number divides $1$, so $\gcd(a,n) = 1$.
(RRA argument shows you that by assuming there is a prime $p|d=\gcd(a,n)$, you can factor $p(a'x - bn') = 1\Rightarrow p|1$, absurd.)
(ii) If $\gcd(a,n) = 1$, then we have $ax\equiv y\pmod{n}$ for arbitrary units $x\not\equiv y$ and $y$ must assume the value $1$ for some value of $x$ since $\{au_1,\ldots , au_{\phi(n)}\}$ is a reduced residue system modulo $n$ (the set of units mod $n$).
(By RRA, suppose you test all $\phi(n)$ units for $x$ but none yields $ax\equiv 1\pmod{n}$. Thus $y$ assumes less than $\phi(n)$ values. So we have a repetition such that $av\equiv u\equiv av'\pmod{n}\Rightarrow v\equiv v'\pmod{n}$ for two different units $v, v'$, contradicting $x\not\equiv y$.)
By Euler's Theorem , $a^{\phi(n)} = 1 (\mathrm{mod}~n)$ if $n$ and $a$ are co-prime. Thus, you can directly take $x = a^{\phi(n) - 1}$ to satisfy the equation.