Theorem 3-5. If $a_1,a_2,\ldots,a_m$ is a complete residue system $\pmod m$ and $\gcd(k,m)=1$, then $ka_1,ka_2,\ldots,ka_m$ also is a complete residue system $\pmod m$
Proof: We show directly that properties (a) and (b) below hold for this new set
A set $a_1,\ldots,a_m$ called a complete residue system modulo $m$, is characterized by the following properties.
a) if $i \neq j$, then $a_i \not\equiv a_j \pmod m$
b) If a is any integer, there is an index i with $1 \leq i \leq m$ for which $a\equiv a_i\pmod m$
a) if $ka_i \equiv ka_j(mod$ $m)$, then by Theorem $3-3$, $a_i \equiv a_j(mod$ $ m)$, whence $i =j$
b) Theorem 2-6 shows that of $(k,m)=1$, the congruence $kx \equiv a \pmod m$ has a solution for any fixed $a$. Let a solution be $x_0$. Since $a_1,\ldots,a_m$ is a complete residue system, there is an index $i$ such that $x_0 \equiv a_i\pmod m$. Hence $kx_0 \equiv ka_i \equiv a \pmod m$.
Prove a theorem similar to theorem $3-5$ concerning numbers $ka_1 + l$,$ka_2 + l$,…..,$ka_m + l$
I am just wondering if we have to use the exact same proof hence we can just set the mod expression as:
$$ka_i+l \equiv ka_j+l (mod m) $$
subtract l from both sides and then apply the same proof.
..
.
New Proof
if $ka_i+l \equiv ka_j+l(mod$ $ m)$
then $m|ka_j+l-ka_i-l$, $m|ka_j-ka_i$
but $(k,m)=1$, so $m|a_j-a_i$,so $j=i$. Property 1 holds
if $(k,m)=1$, so there exists integers x,y such that $kx+my=1$. This implies
$kx \equiv 1 (mod$ $ m)$
let $n\in Z$, so $nx \in Z$
$nx \equiv a_i(mod$ $ m)$
$k*nx \equiv ka_i(mod$ $ m)$
$knx+l \equiv ka_i+l(mod$ $ m)$
$but kx \equiv 1 (mod$ $ m)$
$nkx \equiv n(mod$ $ m)$
$nkx+l \equiv n+l(mod$ $ m)$
we can conclude that $n+l \equiv ka_i+l(mod$ $ m)$. n+l is any integer
I wrote this proof based on the proof that my teacher provided in class. How does that look?
Best Answer
To show that $ka_1, ka_2, \ldots, la_m$ is a complete residue system, it is enough to show that they are all distinct. This follows since $\gcd(k,m) = 1$.