# $a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n)$.

Let $n \in Z$, $n > 1$ and let $a \in Z$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n)$.

Proof: Suppose $(a,n) = 1$. Then $ax + ny = 1$ for some integers $x,y$. Then $ny = 1 - ax$. So $n$ divides $1 - ax$ So $ax \equiv 1 (mod n)$. Let $x = k$. Is this a correct approach? Any help would be appreciated . Thank you in advance.

• I think there's no problem with that. – Mohsen Shahriari Aug 28 '15 at 5:03
• Notice you do not need the restrictions on $n$ or $a$ either. You only need the stipulation $n \neq 0$. – Ishfaaq Aug 28 '15 at 5:04
• A side remark: saying "$k := x$" in the end is more "logical"... – Megadeth Aug 28 '15 at 5:06