Question

3. A collection of n integers an, ..., An is said to form a complete set of residues (or complete system of residues) modulo n if every integer is congruent modulo n to one and only one of ak (or, equivalently, a1,..., an are congruent modulo n to 0,1,2,...,n - 1). Prove the following statement: If an,..., an is a complete set of residues modulo n and gcd(a, n) = 1, then aan,..., aan is also a complete set of residues modulo n.

From A First Course In Number Theory.
Note, we are looking for a lot of detail. Please don't leave out any steps.

Answer 1

m. T We first prove the following lemma : Temma . A set of m incongruent integers modulo - m forms a complete residue system modulo hoof: We will prove this lemma contradiction.. • Suppose that the set of m inderous does not form a complete residuet system modello m. Then we can find atleast one integer a that Te not congruent to any element in this set. Hence non of the elements of this set is actually Congruent to the remaindea when a s divided by m. Thus the dividing by n gields to almost mill remainders. Therefore by the progen hole principle atleast two integers in the set have the same remainder moduló m. This is a contradiction since the set of integer is formed of m integers that are incongruent modulo m. Now suppose aig an do a complete seat of reesidues modulo n and ged (an) 1. We need to show that aqua, aq, is also complete set of residue modulo n. for this, it is sufficient to show that I aa..., aan forms a set of incongruent integers modulo n. for subbose there entist as such ľ, 1 such had b aai aag (modn2 - Since ged(a, n ) = 1 ais ag (moon) which is a contradiction . Hence there are n inequivalent integers modulo n and thus by Comma form a complete sees i due system moduloh -