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.

  • 1
    $\begingroup$ Theorem 2-6 is simply Bézout's identity $\endgroup$ – Kenny Lau Jun 26 '16 at 2:54
  • $\begingroup$ 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$. $\endgroup$ – 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).$

  • $\begingroup$ $(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. $\endgroup$ – Bill Dubuque Jun 26 '16 at 16:06
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Jun 26 '16 at 16:21
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jun 26 '16 at 16:28

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.