Fix a natural number . A residue system mod is a set of integers such that every integer is congruent mod to a unique element of . Suppose and are both residue systems mod ; prove that and are relatively prime.
First suppose . In this case, the only residue system is . Certainly then is only a residue system if ; thus 1 is a greatest common divisor of and , and hence these two are relatively prime.
Now suppose and that and are residue systems mod . In particular, there exists such that mod . Say , so that . Thus 1 is a greatest common divisor of and , so that these are relatively prime.