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.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: