Find the least positive integer $x$ such that $x \equiv 5 ~(mod ~7)$ , $x \equiv 7 ~(mod ~11)$ , $x \equiv 3 ~(mod ~13)$.

 Example: Find the least positive integer $x$ such that 

$x \equiv 5 ~(mod ~7)$,

$x \equiv 7 ~(mod ~11)$,

$x \equiv 3 ~(mod ~13)$.

Answer: Let $ n = 7 \cdot 11 \cdot 13 = 1001, ~N_{1} = \dfrac{n}{7} = \dfrac{1001}{7} = 143, ~ N_2 = \dfrac{n}{11} = \dfrac{1001}{11} = 91, ~ N_3 = \dfrac{n}{13} = \dfrac{1001}{13} = 77$.

Now, we find solution of linear congruences

$143 x_{1} \equiv 1 ~(mod ~7), ~ 91 x_2 \equiv 1 ~(mod ~11),  77x_3 \equiv 1 ~(mod ~13)$

We will find solution of linear congruences $143x_{1} \equiv 1 ~(mod ~7), ~ 91 x_2 \equiv 1 ~(mod ~11),  77x_3 \equiv 1 ~(mod ~13)$ by trial and error method.  Firstly we find solution of linear congruence $143 x_{1} \equiv 1 ~(mod ~7)$. We will consider simple values of $x_{1}$ as $1, ~-1,~ 2,~ -2,~ \cdots $ and check which value satisfy given linear congruence $143 x_{1} \equiv 1 ~(mod ~7)$. When we take $x_{1} = 1, ~-1,~ 2,~ -2,~3, ~ -3$, we observe that $x_{1} =1, ~-1,~ 2$ are not a solution of $143 x_{1} \equiv 1 ~(mod ~7)$. Now, we take $x_{1} =  - 2$, we observe that $x_{1} = - 2$ is  a solution of $143 x_{1} \equiv 1 ~(mod ~7)$. 

We use same method to find solution of $91 x_2 \equiv 1 ~(mod ~11),  77x_3 \equiv 1 ~(mod ~13)$. We observed that $x_2 = 4$ is a solution of $91 x_2 \equiv 1 ~(mod ~11)$, also $x_3 = - 1$ is a solution of  $  77x_3 \equiv 1 ~(mod ~13)$. Thus, a solution of the system of given linear congruences is given by 

$x = 5 \cdot 143 \cdot ( - 2 )+ 7 \cdot 91 \cdot 4 + 3 \cdot 77 \cdot (- 1) = 887 $

modulo $1001$. Thus $887$ is the least positive solution.

Popular posts from this blog

Solve the system of linear congruences $x \equiv 2 ~(mod ~3)$ , $x \equiv 3 ~(mod ~5)$, $x \equiv 2 ~(mod ~7)$.

Example: Solve the system of linear congruences $x \equiv 2 ~(mod ~3)$, $x \equiv 3 ~(mod ~5)$, $x \equiv 2 ~(mod ~7)$. Answer:   Let $ n = 3 \cdot 5 \cdot 7 = 105, ~N_{1} = \dfrac{n}{3} = \dfrac{105}{3} = 35, ~ N_2 = \dfrac{n}{5} = \dfrac{105}{5} = 21, ~ N_3 = \dfrac{n}{7} = \dfrac{105}{7} = 15$. Now, we find solution of linear congruences $35 x_{1} \equiv 1 ~(mod ~3), ~ 2 1 x_2 \equiv 1 ~(mod ~5),  15x_3 \equiv 1 ~(mod ~7)$ We will find solution of linear congruences $35 x_{1} \equiv 1 ~(mod ~3), ~ 2 1 x_2 \equiv 1 ~(mod ~5),  15x_3 \equiv 1 ~(mod ~7)$ by trial and error method.  Firstly we find solution of linear congruence $35 x_{1} \equiv 1 ~(mod ~3)$. We will consider simple values of $x_{1}$ as $1, ~-1,~ 2,~ -2,~ \cdots $ and check which value satisfy given linear congruence $35 x_{1} \equiv 1 ~(mod ~3)$. When we take $x_{1} = 1, ~-1,~ 2,~ -2,~3, ~ -3$, we observe that $x_{1} =1, ~-1,$ are not a solution of $35 x_{1} \equiv 1 ...
Read more

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$. P roof: 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_...
Read more

Solve the linear congruence $18x \equiv 30 ~(mod ~42)$.

Example: Solve the linear congruence $18x \equiv 30 ~(mod ~42)$.   Answer: Since $gcd(18, 42) = 6$ and $6$ divides $30$, by  Theorem , given linear congruence $18x \equiv 30 ~(mod ~42)$ has $6$ mutually incongruent solutions modulo $42$.  We will find first solution by trial and error method. We will consider simple values of $x$ as $1, ~-1,~ 2,~ -2,~ \cdots $ and check which value satisfy given linear congruence $18x \equiv 30 ~(mod ~42)$. When we take $x = 1, ~-1,~ 2,~ -2,~3, ~ -3$, we observe that $x =1, ~-1,~ 2,~ -2,~3$ are not a solution of $18x \equiv 30 ~(mod ~42)$. Now, we take $x = -3$, we observe that $x = -3$ is  a solution of $18x \equiv 30 ~(mod ~42)$. But $-3 \equiv 39 ~ (mod~ 42)$, So $x_{0} = 39$ is a solution of a given  linear congruence $18x \equiv 30 ~(mod ~42)$.  By Theorem , other solutions of given linear congruence $18x \equiv 30 ~(mod ~42)$  are given by  $x_{1} = 39 + \frac{42}{6} = 39 + 7 = 46 \equiv 4~ (mod ~ 42)$,...
Read more