Are $a$ and $n$ relatively prime?

Question

Suppose that $a$ and $n$ are integers, $n>1$. Prove that the equation $ax\equiv1(\mod n)$ has a solution if and only if $a$ and $n$ are relatively prime. How to solving this problem?

Answer 1

Suppose $ax \equiv 1(\mod n)$, then $ax - 1 = bn$ for some $b \in \mathbb{Z}$. So $1 = ax - bn$. So if $gcd(a,n) > 1$, then $gcd(a,n) | ax$, and $gcd(a,n) | bn$. So $gcd(a,n) | ax - bn = 1$, a contradiction. So $gcd(a,n) = 1$. Conversely, if $gcd(a,n) = 1$, then there are $x, b \in \mathbb{Z}$ such that $ax + bn = 1$. This means $ax \equiv 1(\mod n)$.

Answer 2

So $n \cdot y = a \cdot x - 1$ for some $y$. Rearrange this equation into the definition of $(a,n)=1$.

Answer 3

Consider the set of numbers $pa+qn$. If $M,N$ are numbers of this form so are the numbers $cM+dN$.

Now suppose $d$ is the least positive integer expressible in this form, and that $e$ is any positive integer represented in this way. Then $e=sd+r$ with $0\le r \lt d$ and $r=e-sd$ is represented. Since $d$ was the least positive integer and $r\lt d$ we must have $f=0$ and $e=sd$.

Hence any representable positive integer is divisible by $d$. So $a=1\cdot a+0 \cdot n$ is divisible by $d$ and so is $n$. Since $a$ and $n$ are relatively prime, and both are multiples of $d$, we must have $d=1$.

Now if $pa+qn=1$ we have $pa\equiv 1$ mod $n$.

Note this also can be used to show that the hcf $(a,n)=d$ can be represented in the form $pa+qn=d$ in the case that $a$ and $n$ are not relatively prime.

Answer 4

$\exists x\in\Bbb Z\!:\ ax\equiv c\pmod n\!\iff\! \exists x,y\in\Bbb Z\!:\ ax+ny = c\!\overset{\rm\ Bezout}\iff\!\gcd(a,n)\mid c.\ $ Let $\ c = 1.$