Exercise 841Number theory › CongruencesL1Added 3 Nov 2026

Coprimality via congruences

#coprime#congruence#linear combination

Statement

Show that $\gcd(a,n)=1$ iff the congruence $ax\equiv1\pmod n$ has a solution.

Hint

$ax\equiv1\pmod n$ iff $n\mid ax-1$ , iff $ax-1=kn$ , iff $ax-kn=1$ , iff Bézout.

Show solutionHide solution

Forward. If $\gcd(a,n)=1$ , Bézout gives $au+nv=1$ , so $au\equiv1\pmod n$ : $x=u$ is a solution.

Converse. If $ax\equiv1\pmod n$ , then $ax-1=kn$ for some $k$ , so $ax-kn=1$ . Any common divisor of $a,n$ divides $1$ , so $\gcd(a,n)=1$ .

Conclusion. $a$ is invertible mod $n$ iff $\gcd(a,n)=1$ .