coprime divisibility: is $ax-1$ divisible by $n$?

Question

Suppose that $a,n \in \Bbb Z$ are coprime. Show that there is an integer $x$ such that $ax−1$ is divisible by $n$.

I know that $\gcd(a,n)=1$ and feel like that will be used in the proof of this, but the fact that there are no numbers is making it complicated. Do I have to work out the gcd backwards?

Answer 1

Let $I=a\mathbb{Z}+n\mathbb{Z}$ be an ideal in $\mathbb{Z}$. Now, $\mathbb{Z}$ is a PID; i.e., we have $I=d\mathbb{Z}$ for some $d$. But since $a,n\in I$, we have that $a,n\in d\mathbb{Z}$; i.e., $d$ divides both $a$ and $n$. But $gcd(a,n)=1$, so $d=\pm 1$. This proves that $I=\mathbb{Z}$; in particular, $1\in I$, so $1=ax+ny$ for some $x,y\in\mathbb{Z}$. This is what you wanted to prove.

Answer 2

$\gcd(a, n) = 1 \Longrightarrow \exists x, y \in \Bbb Z, \; ax + ny = 1; \tag 1$

$ax + ny = 1 \Longrightarrow ax - 1 = -ny \Longrightarrow n \mid ax - 1. \tag 2$