Algebra Solutions: If two integers are relatively prime, then they are invertible mod each other

If two integers are relatively prime, then they are invertible mod each other

Let $n \in \mathbb{Z}$ , $n > 1$ , and let $a \in \mathbb{Z}$ with $1 \leq a \leq n$ . Prove that if $a$ and $n$ are relatively prime then there is an integer $c$ with $ac = 1 \mod n$ .

Suppose $a$ and $n$ satisfy the hypotheses, with $\mathsf{gcd}(a,n) = 1$ . Then there exist integers $c$ and $b$ such that $ac + nb = 1$ . Reducing mod n gives $ac = 1 \mod n$ .

Algebra Solutions

If two integers are relatively prime, then they are invertible mod each other

No comments:

Post a Comment