Mathematics

 Definition: Let $n$ be a fixed positive integer. Two integers $a$ and $b$ are said to be congruent modulo $n$}  denoted by $a \equiv b ~(mod ~n)$ if $n$ divides the difference $a - b$; that is, provided that $a - b = k \cdot n$ for some integer $k$.  Now we give an equivalent  definition of congruent modulo $n$   Definition:  Let $n$ be a fixed positive integer. Two integers $a$ and $b$ are said to be \congruent modulo $n$,  denoted by $a  \equiv  b ~(mod~ n)$  if $b$ is a remainder when $a$ is  divided by $n$.  Let $n = 5$, we can observe that $10  \equiv  0 ~(mod~ 5)$ Since $5$ divides $10-0= 10$. Similarly,  we can see that $21  \equiv  1 ~(mod~ 5)$ Since $5$ divides $21-1= 20$, $37  \equiv  2 ~(mod~ 5)$ Since $5$ divides $37-2= 35$, $43  \equiv  3 ~(mod~ 5)$ Since $5$ divides $43-3= 40$, $59  \equiv  4 ~(mod~ 5)$ Since $5$ divides $59-4= 55$. When $ n \nmi...

  Let $a$ and $b$ be two integers, not both of them are zero. Then  Euclidean  Algorithm to find  greatest common divisor of $a$ and $b$ is as follows. Since $gcd(|a|,|b|) = gcd(a,b)$, without loss of generality, assume that $0 < b \leq a$. Step $(1)$ Apply Division Algorithm for integers $a$ and $b$, so there exist integers $q_{1}$ and $r_{1}$ such that  $a = b \cdot  q_{1} + r_{1}$, where $0 \leq r_{1} < b$.   If $r_{1} = 0$, then $b ~|~ a$ and hence $b = gcd(a,b)$. If $r_{1} \not = 0$,  then go to step $(2)$. Step $(2)$ Apply Division Algorithm for integers $b$ and $r_{1}$, so there exist integers $q_2$ and $r_2$ such that  $b = r_{1}  \cdot q_2 + r_2$, where $0 \leq r_2 < r_{1}$.  If $r_2 = 0$, then stop.  If $r_2 \not = 0$, then go to step $(3)$. Step $(3)$ Apply Division Algorithm  for integers $r_{1}$ and $r_2$, so there exist integers $q_3$ and $r_3$ such that  $r_{1} = r_2 \cdot q_3 + ...

  Lemma:  Let $a, ~b, ~q, ~r $ be integers such that $a = b \cdot q +r$, where $0< r < b$, then $gcd(a,b) = gcd(b,r)$.  Proof:  Let $gcd(a,b) = d$. Firstly, we show that $d$ is a common divisor of both $b$ and $r$. Since $gcd(a,b) = d$, $d ~|~ a$ and $d ~|~ b$. Therefore by part $7.$ of Theorem , $d ~|~ (a~ -~ b \cdot q)$, i.e. $d ~|~ r$. Thus, $d$ is a common divisor of both $b$ and $r$. Now, we show that $d$ is greatest among all common divisors of both $b$ and $r$. Let $c$ be  an arbitrary common divisor of $b$ and $r$, then by part $7.$ of Theorem , $c ~|~ (b \cdot q + r)$, i.e. $c ~|~ a$. This implies that  $c$ is a common divisor of $a$ and $b$, so that $c \leq d$. This gives $d$ is greatest among all common divisors of both $b$ and $r$ and so  $gcd(b,r ) = d $.

Corollary: If $a$ and $b$ are any integers, not both them are zero, then the set  $T = \{a \cdot x+ b \cdot y \;|\; x, y \in \mathbb{Z}\}$ is the set of all multiples of $d = gcd(a,b)$. Proof:  Since $d = gcd(a,b)$, we have  $d ~|~ a$ and $d ~|~ b$. By part $7.$ of Theorem ,  $d ~|~ (a \cdot x + b  \cdot y)$ for all integers $x, ~y$. Thus, every member of $T$ is a multiple of $d$. Conversely, Since $d = gcd(a,b)$,With the help of   Theorem , there exist integers $x'$ and $y'$ such that $gcd(a, b) =a \cdot x'+ b \cdot y'$. So that any multiple $n \cdot d$ of $d$ is of the form $n \cdot d = n~(a \cdot x' + b \cdot y') = a~(n \cdot x') + b~(n \cdot y')$. Hence, $n\cdot d$ is a linear combination of $a$ and $b$, and hence lies in $T$.

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

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

  Corollary: If $a$ and $b$ are integers, with $b \not = 0$, then there exist unique integers $q$ and  $r$ such that  $a= b \cdot q + r$ where  $0 \leq  r <|b|$. Proof: Consider the case in which $b$ is negative. So $|b| > 0$. By  Division Algorithm Theorem , there exist unique integers $q'$ and $r$ such that \linebreak $a=  |b| \cdot  q'+ r$ where  $0 \leq  r <|b|$. Note that $|b | = - b$, we can take $q = -q'$ to get $a= q \cdot b + r$,  where  $0 \leq  r <|b|$. Consider the case in which $b$ is positive. Proof follows from Division Algorithm Theorem .

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