A set of n integers is a complete residue modulo n if no two elements are congruent mod n.
I understand the theorem but how do I go about proving it? Any help would be appreciated!
My attempt.
Theorem 3.17 states
Let n be a natural number. Any set {a1,a2,…,an} of n integers for which no two are congruent is a complete residue system modulo n.
Intuitively, this makes sense, if no two are congruent, then they all have distinct remainders .
Proof by contradiction applying the pigeon hole principal(have never used it in a proof).
Suppose we have a set of n integers, call it
A={a1,a2,…an}
in which no two are congruent modulo n and suppose we have a residue set
R={r1,r2…rn-1}
where we have less than n residues.
Since a1 is not congruent mod n to any ai for 1
Since a2 is not congruent mod n to any ai for 2
Now, an is not congruent to any ai mod n for any 1<=i<=n-1, so by the D.A, an=n(qn)+rn, which implies that an is congruent to rn mod n, but this is impossible since R has fewer than n elements(remainders), so an is congruent to some ai for some n<=i<=1 , but this contradicts that an is not congruent to any ai.
Best Answer
If v = r mod n and w = r mod n then v = w mod n.
By definition a complete residue modulo n is some set of n integers {$r_i$} where no two are congruent to each other. What we need to prove is that any other such set {$s_i$} of n integers is also a complete residue.
Well {$r_i$} being a complete residue means, each $s_i = r_j \mod n$ for some $r_j$. Another $s_k$ where $s_k \ne s_i$ is congruent to some $r_l$. If $r_l = r_j$ the $s_i$ an $s_k$ are congruent to each other. Thus each $s_k$ is congruent to a different $r_j$ and thus each $s_i$ is in a unique congruency class and as {$r_i$} represents all classes and there is a direct correspondence between {$r_i$} and {$s_i$}, {$s_i$} is a complete residue.