# I need an explanation of a theorem about congruence

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$

I am having troubles understanding property b

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

The book mentions the existence of a theorem 2-6, but it doesn't exists, so I need an explanation about it.

• Theorem 2-6 is simply Bézout's identity – Kenny Lau Jun 26 '16 at 2:54
• Property (a) says that no two of the $a_i$'s are the same. Property (b) says that they are a complete set of residues. Given any integer you choose, it's congruent to some $a_i$. – user4894 Jun 26 '16 at 3:00

Reference : See : Euclid's Algorithm.

Theorem (Euclid). If integers $k,m$ are co-prime (i.e. $\gcd (k,m)=1$), then there exist integers $u, v$ with $k u+m v=1.$... So $u$ is a solution of $k x\equiv 1\pmod m ,$ and $u a$ is a solution of $k x\equiv a \pmod m.$

Important corollaries to this theorem include

(1) The fundamental theorem of arithmetic :If $a| b c$ and $\gcd (a,b)=1$ then $a|c.$

(2) Unique factorization : Let $p_1,...,p_m$ and $q_1,...,q_n$ be primes with $p_i\leq p_{i+1}$ for $1\leq i<m,$ and with $q_j\leq q_{j+1}$ for $1\leq j<n.$ Then $(\prod_{i=1}^mp_i=\prod_{j=1}^nq_j)\implies (m=n \land p_i=q_i$ for all $1\leq i\leq m).$

(3) For integers $a, b$, not both $0$ there exist integers $x,y$ with $a x +b y=\gcd (a,b).$

• $(1)$ is normally called Euclid's (or Gauss') Lemma, not FTA (= existence and uniquness of prime factorizations), and $(3)$ is called the Bezout gcd identity. – Bill Dubuque Jun 26 '16 at 16:06
• OK.I recall a text that called (1) the FTA. I'm not much concerned with labels, but I dk why it would be called Gauss' Lemma. – DanielWainfleet Jun 26 '16 at 16:21
• I don't doubt that some author used that name for $(1)$. But it is not common. The more common names have to do with Euclid giving a (partial) proof of it, and Gauss giving a full proof. But the name "Gauss' Lemma" is already used for too many things. – Bill Dubuque Jun 26 '16 at 16:28