Elementary Properties of Congruences: Let $n > 1$ be fixed and $a,~ b,~ c,~ d$ be arbitrary integers. Then the following properties hold: 1) $a \equiv a ~(mod ~n)$. 2) If $a \equiv b ~(mod ~n)$, then $b \equiv a ~(mod ~n)$. 3) If $a \equiv b ~(mod ~n)$ and $b \equiv c ~(mod ~n)$, then $a \equiv c ~(mod ~n)$. 4) If $a \equiv b ~(mod ~n)$ and $c \equiv d ~(mod ~n)$, then $a + c \equiv b + d ~(mod ~n)$ and $a \cdot c \equiv b \cdot d ~(mod ~n)$. 5) If $a \equiv b~ (mod ~n)$, then $a + c \equiv b + c ~(mod ~n)$ and $a \cdot c \equiv b \cdot c ~(mod ~n)$. 6) If $a \equiv b~ (mod ~n)$, then $a^k \equiv b^k ~(mod ~n)$ for any positive integer $k$. 7) If $a \equiv b~ (mod ~n)$ and $d> 0$ such that $ d \mid n$, then $a \equiv b ~(mod ~d)$.

Elementary Properties of Congruences: Let $n > 1$ be fixed and $a,~ b,~ c,~ d$ be arbitrary integers. Then the following properties hold: 

1) $a  \equiv a ~(mod ~n)$.

2)  If $a \equiv b ~(mod ~n)$, then $b \equiv a ~(mod ~n)$. 

3) If $a \equiv b ~(mod ~n)$ and $b \equiv c ~(mod ~n)$, then  $a \equiv c ~(mod ~n)$. 

4) If $a \equiv b ~(mod ~n)$ and $c \equiv d ~(mod ~n)$, then  $a + c \equiv b + d ~(mod ~n)$ and $a \cdot c \equiv b \cdot d ~(mod ~n)$. 

5) If $a \equiv b~ (mod ~n)$, then $a + c \equiv b + c ~(mod ~n)$ and $a \cdot c \equiv b \cdot c ~(mod ~n)$. 

6) If $a \equiv b~ (mod ~n)$, then $a^k \equiv  b^k ~(mod ~n)$ for any positive integer $k$.

7)   If $a \equiv b~ (mod ~n)$ and $d> 0$ such that $ d \mid n$, then $a \equiv  b ~(mod ~d)$.


Proof: $1.$ For every integer $a$, we have $a - a = 0$ and $n ~|~ (a -a = 0)$. Therefore by definition of congruences $a  \equiv a ~(mod ~n)$.

$2.$ Suppose that $a \equiv b ~(mod ~n)$. Therefore $a = b + n \cdot k$ for some integer $k$. We can write $b$ as $b = a - n \cdot k = a + (- k ) \cdot n$, where $(- k)$ is an integer. So by definition of congruences $b  \equiv a ~(mod ~n)$.

$3.$ Suppose that  $a \equiv b ~(mod ~n)$ and $b \equiv c ~(mod ~n)$. So that  $a = b + n \cdot k_{1}$ for some integer $k_{1} $ and  $b = c + n \cdot k_2$ for some integer $k_2$. Put $b = c + n \cdot k_2$ in $a = b + n \cdot k_{1}$. Therefore $a = b + n \cdot k_{1} = c + n \cdot k_2 + n \cdot k_{1} = c + n  \cdot (k_{1} + k_2)$, where $(k_{1} + k_2)$ is an integer. So by definition of congruences $a  \equiv c ~(mod ~n)$.

$4.$ Suppose that  $a \equiv b ~(mod ~n)$ and $c \equiv d ~(mod ~n)$. So that  $a = b + n \cdot k_{1}$ for some integer $k_{1} $ and  $c = d + n \cdot k_2$ for some integer $k_2$. Therefore $a + c = b +  n \cdot k_{1} + d + n \cdot k_2 = b + d + n  \cdot (k_{1} + k_2)$, where $(k_{1} + k_2)$ is an integer. So by definition of congruences $a + c \equiv b + d ~(mod ~n)$. We have $a \cdot c = (b + n \cdot k_{1}) \cdot (d + n \cdot k_2) = b \cdot d + b \cdot n \cdot k_2 + d \cdot  n \cdot k_{1} +  n \cdot k_{1}\cdot  n \cdot k_2 = b \cdot d + n \cdot (b \cdot k_2 + d \cdot k_{1} +  n \cdot k_{1} \cdot  k_2 )$, where $(b \cdot k_2 + d \cdot k_{1} +  n \cdot k_{1} \cdot  k_2 )$ is an integer. So by definition of congruences $a ~c  \equiv b ~d ~(mod ~n)$.

$5.$ Since $a \equiv b ~(mod ~n)$ and $c \equiv c ~(mod ~n)$ so  $5.$ follows from $4.$ 

$6.$ Suppose that  $a \equiv b ~(mod ~n)$. we prove property $6.$ with the help of Mathematical Induction. The statement certainly 

holds for $k = 1$, and we will assume it is true for some fixed $k$. From $4.$, we know  that  $a \equiv b ~(mod ~n)$ and $a^k \equiv b^k ~(mod ~n)$ together imply that $a \cdot a^k \equiv b \cdot b^k ~(mod ~n)$, or 

equivalently  $a^{k+1} \equiv b^{k+1} ~(mod ~n)$. This is the form the statement should take for $k + 1$ and so the induction step is complete. Therefore $a^k \equiv  b^k ~(mod ~n)$ for any positive integer $k$. 

$7.$ Suppose that $a \equiv b ~(mod ~n)$ and $d > 0$ such that $d \mid n$. Therefore there exist integers $k_{1}, ~k_2$ such that   $a = b + n \cdot k_{1}$ and $n = d \cdot k_2$. We put $n = d \cdot k_2$ in $a = b + n \cdot k_{1}$, so $a = b + (d \cdot k_2) \cdot k_{1} = b + d \cdot (k_{1} \cdot k_2)$, where $k_{1} \cdot k_2$ is an integer. This gives that $a \equiv b ~(mod ~ d)$.

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

Define Greatest Common Divisor and Prove that if $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$.

Image
Definition: Let $a$ and $b$ be any integers, with at least one of them is not zero. The greatest common divisor of $a$ and $b$, denoted by $gcd(a, b)$, is the positive integer $d$ satisfying the following: $1.$  $d ~|~ a$ and $d ~|~ b$. $2.$ If $c ~|~ a$ and $c ~|~ b$, then $c \leq d$. Theorem:  If $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$. Proof:   Let  $a$ and $b$ be any integers, not both of them are zero. Consider the set $S = \{a \cdot u + b \cdot  v \;|\; a \cdot  u + b \cdot  v > 0$ and $ u, v \in \mathbb{Z}\}$, that is  $S$ is the set of all positive linear combinations of $a$ and $b$. Firstly, we will show  that $S$ is nonempty set. We have taken integers $a$ and $b$ such that not both of them are zero. Without loss of generality, suppose that $a \not = 0$. Then the integer $|a| = a \cdot u + b \cdot 0 \in S$ for the v...
Read more