A fact about residue systems

Fix a natural number n. A residue system mod n is a set S of integers such that every integer is congruent mod n to a unique element of S. Suppose S and bS are both residue systems mod n; prove that b and n are relatively prime.


First suppose n = 0. In this case, the only residue system is \mathbb{Z}. Certainly then b\mathbb{Z} is only a residue system if b = \pm 1; thus 1 is a greatest common divisor of n and b, and hence these two are relatively prime.

Now suppose n > 0 and that S and bS are residue systems mod n. In particular, there exists s \in S such that bs \equiv 1 mod n. Say kn = bs - 1, so that bs - kn = 1. Thus 1 is a greatest common divisor of b and n, so that these are relatively prime.

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: