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?

  • $\begingroup$ Yes, you can use the same proof. $\endgroup$
    – Kenny Lau
    Jun 26, 2016 at 4:23
  • $\begingroup$ In order to find the residue class for a general integer $a$, you can consider the class for $a-l$ in the previous system. $\endgroup$
    – Joffan
    Jun 26, 2016 at 4:41
  • $\begingroup$ 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.\ $ $\endgroup$ Jun 26, 2016 at 16:01

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.