Suppose that $a$ is co-prime to $n$. Prove that there exists $z ∈ Z$ such that $az \equiv 1 \pmod n$

Question

So here's the question: Suppose that $a$ is co-prime to $n$. Prove that there exists $z ∈ Z$ such that $az \equiv 1 \pmod n$

So, what I was thinking was that by Bezout's Lemma, we have hcf$(a,n)=1$ and so $az=n-1$ but the I can't turn that to a plus one. I don't see how to do this?

Answer 1

You know there is a $z$ such that $az \equiv -1 \pmod n$. What happens if you multiply both sides by $-1?$

Answer 2

By Bezout's lemma you have that there are $k,t\in\mathbb{Z}$ such that $nk+at=1$. So, $nk=1-at$, and then $n|(1-at)$. Take $z=-t$ so, $az\equiv1(mod\ n)$.