Define a complete set of residues or a complete system of residues

 Definition:  The set of $n$ integers $0, ~1, ~2, ... ,~ n - 1$ is called the set of least nonnegative residues  modulo $n$. In general, a collection of $n$ integers $a_{1},~ a_2, \cdots ,~ a_n$ is said to form a complete set of residues or a complete system of residues modulo $n$ if every integer is congruent modulo $n$ to one and only one of the $a_k$ where $1\leq k \leq n$.

We can observe that The set of $5$ integers $0, ~1, ~2, ~3,~ 4$ is  the set of least nonnegative residues modulo $5$ and a collection of $5$ integers $10, ~21, ~37, ~43, ~59$  form a complete set of residues (or  a complete system of residues ) modulo $5$. Observe that any $n$ integers form a complete set of residues modulo $n$ if and only if no two of the integers are congruent modulo $n$.

Remark: Note that for given integer $n > 0$, negative integer can  form a complete set of residues (or  a complete system of residues ) modulo $n$. For example $59 \equiv 4 ~(mod~ 5)$ and $4 \equiv -1 ~(mod~ 5)$. Therefore  $59 \equiv -1 ~(mod~ 5)$. Also $43 \equiv 3 ~(mod~ 5)$ and $3 \equiv -2 ~(mod~ 5)$. Therefore $43 \equiv -2 ~(mod~ 5)$. We have $37 \equiv 2 ~(mod~ 5)$ and $2 \equiv -3 ~(mod~ 5)$. Therefore $37 \equiv -3 ~(mod~ 5)$. On the same line $21 \equiv 1 ~(mod~ 5)$ and $1 \equiv -4 ~(mod~ 5)$. Therefore $21 \equiv -4 ~(mod~ 5)$. lastly $10 \equiv 0~(mod~ 5)$ and $0 \equiv -5 ~(mod~ 5)$. Therefore $10 \equiv -5 ~(mod~ 5)$. Hence $-5, ~ -4, ~ -3, ~-2, ~-1$ form a complete set of residues (or  a complete system of residues ) modulo $5$.

Popular posts from this blog

Definition of divisibility and Theorem on divisibility

  Definition: An integer $b$ is said to be divisible by an integer $a \not = 0$, if there exists some integer $c$ such that $ b = a \cdot c$. An integer $b$ is  divisible by an integer $a \not = 0$, is denoted by $a ~|~ b$.  We write $a \nmid b$ to indicate that $b$  is not divisible by $a$. Theorem: For integers $a, ~b, ~c$ the following hold: $1.$ $a ~|~ 0, ~ 1 ~|~ a, ~ a ~|~ a $. $2.$  $ a ~|~ 1 $ if and only if $a =  1$ or $a = -1$. $3.$  If $a ~|~ b$ and $c ~|~ d$, then $a \cdot c ~|~ b \cdot d$. $4.$   If $a ~|~ b$ and $b ~|~ c$, then $a ~|~ c$. $5.$  If $a ~|~ b$ and $b ~|~ a$ if and only if $a =  b$ or $a = -b$. $6.$  If $a ~|~ b$ and $b \not = 0$, then $|a| \leq |b|$. $7.$  If $a ~|~ b$ and $a ~|~ c$, then $a~ |~ (b \cdot x + c \cdot y)$ for arbitrary integers $x$ and $y$. Proof: $1.$ For any integer $a$, we can write $0 = a \cdot 0$, $a = 1 \cdot a$ and $a = a \cdot 1$. Theref...
Read more

The Division Algorithm / Prove that given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$.

Image
State and prove Division Algorithm theorem.  Theorem:  Given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$. Proof : Firstly, we will show that the set $S = \{a - x \cdot b \;|\; x \in \mathbb{Z}$ and $  a -x \cdot b \geq 0\}$ is nonempty.  For this purpose, we have to find value of $x$ such that $a -x \cdot b \geq 0$. Given that integer $b > 0$, i.e. $b \geq 1$. Multiply $b \geq 1$ by $|a|$, we get $|a|\cdot b \geq |a|$ and so $a - ( - |a|) \cdot b = a + |a| \cdot b \geq a + |a| \geq 0$. If we take $x = |a|$, then, $a -x \cdot b \in S$. This show that $S$ is nonempty subset of nonnegative integers. By the Well-Ordering Principle (for more details see  Well-Ordering Principle  ) , set $S$ contains a least integer; say it $r$. Since $r \in S$, there exists an i...
Read more

State and Prove Fundamental Theorem of Arithmetic. Prove that every positive integer $n > 1$ is either a prime or can be written as a product of primes; this representation is unique, apart from the order in which the factors occur.

  (Fundamental Theorem of Arithmetic): Every positive integer $n > 1$ is either a prime or can be written as a product of primes; this representation is unique, apart from the order in which the factors occur. Proof: If a positive integer $n > 1$ is a prime number, then we are done. So suppose that $n$ is a composite number. Therefore there exists an integer $d$ satisfying $d ~|~ n$ and $1 < d < n$. By Well-Ordering Principle , there exists smallest integer among all such integers $d$ (positive divisors), we will called this smallest integer (smallest positive divisor) as a $p_{1}$. We claim that $p_{1}$ is a prime number. Suppose that $p_{1}$ is not a prime number. So there exists  an integer $q$ satisfying $q ~|~ p_{1}$ and $1 < q < p_{1}$. Since $q ~|~ p_{1}$ and $p_{1} ~|~ n$, we will get $q ~|~ n$, a contradiction to choice of smallest positive divisor  $p_{1}$ of $n$. Therefore we can write $n$ as $n = p_{1} \cdot n_{1}$, where $p_{1}$ is a pri...
Read more