# Proof about complete residue system

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?

• Yes, you can use the same proof. Jun 26, 2016 at 4:23
• In order to find the residue class for a general integer $a$, you can consider the class for $a-l$ in the previous system. Jun 26, 2016 at 4:41
• You know $\,b_i = ka_i\,$ is a CRS, so it suffices to prove that if $\,b_i$ is a CRS then so too is $\,b_i + l.\$ Jun 26, 2016 at 16:01

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$.