State and Prove Chinese Remainder Theorem.

 Chinese Remainder Theorem. Let $n_{1},~ n_2,~ \cdots,~ n_r$ be positive integers such that $gcd(n_i, n_j) = 1$  for $i \not = j$. Then the system of linear congruences

$x \equiv a_{1} ~(mod ~n_{1})$

$x \equiv a_2 ~(mod~ n_2)$

$x \equiv a_3~ (mod~ n_3)$

$\vdots$

$x \equiv a_r~ (mod ~n_r)$

has a simultaneous solution, which is unique modulo the integer  $n_{1} \cdot n_2 \cdot n_3 ~\cdots~ n_r$.

Proof: Consider $n = n_{1} \cdot n_2 \cdot n_3 ~\cdots~ n_r$. Let $N_k = \dfrac{n}{n_k} = n_{1} \cdot n_2 \cdot n_3 ~\cdots~ n_{k-1} \cdot n_{k+1} ~\cdots ~n_r $ for each $k = 1, ~2, ~3,~ \cdots, ~r $ i.e. $N_k$ is the product of all the integers $n_i$; with the factor $n_k$ omitted. Since $gcd(n_i, n_j) = 1$  for $i \not = j$, we will have $gcd(N_k, n_k) = 1$. By Theorem, the  linear congruence $N_k ~x \equiv 1 ~(mod ~n_k)$, has a solution; call the unique solution $x_k$. We claim that the integer 

$\bar{x} = a_{1} \cdot N_{1} \cdot x_{1} + a_2 \cdot N_2 \cdot x_2 + \cdots + a_r \cdot  N_r \cdot x_r$ is a simultaneous solution of the given system. Since $n_k ~|~ N_i$ for $k \not = i$, we get $N_i \equiv 0 ~(mod~ n_k)$. This gives that $\bar{x} = a_{1} \cdot N_{1} \cdot x_{1} + a_2 \cdot N_2 \cdot x_2 + \cdots + a_r \cdot  N_r \cdot x_r  \equiv a_k \cdot  N_k \cdot x_k ~(mod ~n_k) $. But $x_k$ is a solution of the linear congruence $N_k x \equiv 1 ~(mod ~n_k)$, so that $\bar{x} = a_{1} \cdot N_{1} \cdot x_{1} + a_2 \cdot N_2 \cdot x_2 + \cdots + a_r \cdot  N_r \cdot x_r  \equiv a_k \cdot  1 \equiv a_k ~(mod ~n_k) $. This shows that a solution to the given system of congruences exists.

Now, we prove the uniqueness of the solution. Suppose that $x'$ is any other integer that satisfies these congruences. Then 

$\bar{x} \equiv a_k \equiv x' ~(mod ~n_k) $ where $ k = 1,~ 2,~ \cdots,~ r$. and so $n_k ~|~ \bar{x} -x'$ for each value of $k$. Since $gcd(n_i, n_j) = 1$, by Corollary, $n_{1} \cdot n_2 ~ \cdots~ n_r ~|~ \bar{x} -x'$; hence $\bar{x} \equiv x' ~(mod ~n)$. Hence solution to given system of linear congruences is unique.

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