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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.