Mathematics

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

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

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)$,...

 Example:  Solve the linear congruence $9x \equiv 21 ~(mod ~ 30)$. Answer: Since $gcd(9, 30) = 3$ and $3$ divides $21$, by  Theorem , given linear congruence $9x \equiv 21 ~(mod ~30)$ has $3$ mutually incongruent solutions modulo $30$.  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 $9x \equiv 21 ~(mod~ 30)$. When we take $x = 1$, we observe that $x =1$ is not a solution of $9x \equiv 21 ~(mod ~30)$. Now, we take $x = - 1$, we observe that $x = - 1$ is  a solution of $9x \equiv 21 ~(mod ~30)$. But $-1 \equiv 29 ~(mod ~30) $, therefore $x_{0} = 29$ is a solution of a given  linear congruence $9x \equiv 21 ~(mod ~30)$.  By Theorem , other solutions of given linear congruence $9x \equiv 21 ~(mod ~30)$  are given by $x_{1} = 29 + \frac{30}{3} = 29 + 10 = 39 \equiv 9~ (mod ~ 30), ~ x_2 = 29 + (\frac{30}{3}) ~2 = 29 + 10 \...

  Lemma: Let $p$ be a prime number. Then prove that $x^2 \equiv 1 ~(mod ~p)$ if and only if $x \equiv 1 ~ (mod ~p) $ or $x \equiv - 1 ~ (mod ~p) $. P roof: Suppose that $x^2 \equiv 1 ~(mod ~p)$. This quadratic congruence is equivalent to $(x^2 -1 )\equiv 0 ~(mod ~p)$ i.e.  $(x -1 ) ~(x + 1) \equiv 0 ~(mod ~p)$. This implies that $p ~|~ (x - 1) ~ (x+1)$. By Theorem , $p ~|~ (x - 1)$ or $p ~|~ (x + 1)$. This gives that $x \equiv 1 ~ (mod ~p) $ or $x \equiv - 1 ~ (mod ~p) $. Conversely, suppose that either $x \equiv 1 ~ (mod ~p) $ or $x \equiv - 1 ~ (mod ~p) $. Then clearly $x^2 \equiv 1 ~(mod ~p)$.

  Definition:   Let $a, ~b,  ~n > 0$ be integers and $x$ be a variable then  an equation of the form $ax \equiv b ~(mod ~n)$  is called a linear congruence, and an integer $x_{0}$ for which $a x_{0} \equiv b ~(mod ~n )$ is called a solution of an equation  $ax \equiv b ~(mod ~n)$.  By definition, $a ~x_{0} \equiv b ~(mod~ n)$ if and only  if $n ~|~ a x_{0} - b $ i.e. $a x_{0} - b = n y_{0} $ for some integer $y_{0}$· Thus, the problem of finding all integers that will satisfy the linear congruence $a x \equiv b ~(mod ~n)$ is identical with that of obtaining all solutions of the linear Diophantine equation $ax - ny = b$. Theorem:   The linear congruence $ax \equiv b ~(mod ~n)$ has a solution if and only if $d ~|~ b$, where $d = gcd(a, n)$. If $d ~|~ b$, then it has $d$ mutually incongruent solutions modulo $n$. P roof: In last para, we have observed that the given linear congruence $ax \equiv b ~(mod ~n)$ is equivalent to the linea...

  Example : Show that the integer $111^{333} + 333^{111}$ is divisible by $7$. Answer: Firstly, we will find the remainder when $111^{333} $ and $ 333^{111}$ is divided by $7$. Then with help of property $4.$ of Theorem , we show that  the integer $111^{333} + 333^{111}$ is divisible by $39$. We have $111 \equiv 6 ~(mod ~7)$ but $6 \equiv -1 ~(mod ~7) $. Therefore $111 \equiv -1 ~(mod ~7) $. By property $6.$ of Theorem , we have  $111^{2} \equiv 1 ~(mod ~7)$. We can write $333$ as $333 = 166 \cdot 2 + 1$. Therefore $111^{333} \equiv (111^{2})^{166} \cdot 111 \equiv 1^{166} \cdot 111 \equiv  6 ~(mod ~7)$, i.e. $111^{333} \equiv  6 ~(mod ~7)$. This gives that $6$ is a remainder when $111^{333}$ is divided by $7$. We have $333 \equiv 4 ~(mod ~7)$.  By property $6.$ of Theorem , we have $333^2 \equiv 4^2 \equiv 2 ~(mod ~7)$. Again, with the help of property $6.$ of Theorem , we have  $(333^2)^3 = 333^6 \equiv 2^3 \equiv 1 ~(mod ~7)$. We ca...

Example : Show that the integer $53^{103} + 103^{53}$ is divisible by $39$.  Answer: Firstly, we will find the remainder when $53^{103} $ and $ 103^{53}$ is divided by $39$. Then with help of property $4.$ of Theorem , we show that  the integer $53^{103} + 103^{53}$ is divisible by $39$. We have $53 \equiv 14 ~(mod ~39)$. By property $6.$ of Theorem , we have $53^2 \equiv 14^2 \equiv 1 ~(mod ~39)$. We can write $103$ as $103 = 51 \cdot 2 + 1$. Therefore $53^{103} \equiv (53^{2})^{51} \cdot 53 \equiv 1^{51} \cdot 53 \equiv  14 ~(mod ~39)$, i.e. $53^{103} \equiv  14 ~(mod ~39)$. This gives that $14$ is a remainder when $53^{103}$ is divided by $39$. We have $103 \equiv 25 ~(mod ~39)$. But $25 \equiv -14 ~ (mod ~ 39)$. Therefore $103 \equiv -14 ~(mod ~39)$. By property $6.$ of Theorem , we have $103^2 \equiv (- 14)^2 \equiv 1 ~(mod ~39)$.  We can write $53$ as $53 = 26 \cdot 2 + 1$. Therefore $103^{53} \equiv (103^{2})^{26} \cdot 103 \equiv 1^{26} \...

  Example: Find a remainder when $2^{50}$ is divided by $7$.  Answer: We have $2 \equiv 2 ~(mod ~7) $. By property $6.$ of Theorem ,  we have  $2^{2} \equiv 4 ~(mod ~7)$. On the same line we have $2^{3} \equiv 1 ~(mod ~7)$. We can write $50$ as $50 = 16 \cdot 3 + 2$. Therefore $2^{50} \equiv (2^{3})^{16} \cdot 2^2 \equiv 1^{48} \cdot 2^2 \equiv  4 ~(mod ~7)$, i.e. $2^{50} \equiv  4 ~(mod ~7)$. This gives that $4$ is a remainder when $2^{50}$ is divided by $7$. Example:   Find a remainder when $41^{65}$ is divided by $7$.   Answer: We have $41 \equiv 6 ~(mod ~7) $, but $6 \equiv -1 ~(mod ~7) $. Therefore $41 \equiv -1 ~(mod ~7) $. By property $6.$ of Theorem ,  we have  $41^{2} \equiv 1 ~(mod ~7)$.  We can write $65$ as $65 = 32 \cdot 2 + 1$. Therefore $41^{65} \equiv (41^{2})^{32} \cdot 41 \equiv 1^{32} \cdot 41 \equiv  6 ~(mod ~7)$, i.e. $41^{65} \equiv  6 ~(mod ~7)$. This gives that $6$ is a remainder whe...

 In Theorem we saw that if $a \equiv b ~(mod ~n)$, then $c \cdot a \equiv c \cdot b ~(mod ~n)$ for any integer $c$. What about converse $?$ i.e. if $c \cdot a \equiv c \cdot b ~(mod ~n)$ for any integer $c$ does it implies  $a \equiv b ~(mod ~n) ~ ?$  we give answer to this question as No. Here is an example $2 \cdot 4  \equiv 2 \cdot 1 ~(mod~6)$, but $4 \not\equiv 1 ~(mod ~6)$. In brief: One cannot unrestrictedly cancel a common factor in the arithmetic of congruences.  Theorem:   If $c \cdot a \equiv c \cdot b ~(mod ~n)$, then $a \equiv b ~(mod ~\frac{n}{d} )$, where $d = gcd(c, n)$.  Proof:   Suppose that $c \cdot a \equiv c \cdot b ~(mod ~n)$. Therefore by definition of congruences $c \cdot a ~-~ c \cdot b = n \cdot k$ for some integer $k$. Since  $gcd(c, n) = d$, there exist relatively prime integers $r$ and $s$ such that  $c = d \cdot r,~ n = d \cdot s$. We put $c = d \cdot r,~ n = d \cdot s$ in $c \cdot a - c \cdot b = n \cdo...

 Example:  Find a remainder when $1 !~ + 2  ! ~+ 3  !~ + \cdots ~+ 100  !$ is divided by $12$  Answer:   One can observe that $4! \equiv 24 \equiv 0 ~(mod ~12)$; thus, for $k \geq 4,~ k !  \equiv 4! \cdot 5 \cdot 6 ~\cdots ~k \equiv 0 \cdot  5 \cdot 6 ~\cdots~ k \equiv 0 ~(mod ~12)$. Therefore $1!~ + 2!~ + 3!~ + 4! ~+ \cdots ~+ 100! \equiv 1!~ + 2!~ + 3!~ + ~0 +~ \cdots + ~ 0 \equiv 9 ~(mod ~12) $ i.e. $9 $ a remainder when $1 ! + 2  ! + 3  ! + \cdots + 100  !$ divided by 12.

 Example:  Show that $41$ divide $2^{20} - 1$.   OR   Show that $1$ is remainder when $2^{20}$ is divided by $41$.  OR   Show that $2^{20} \equiv 1 ~(mod ~41)$. Answer:  We have to show that $41$ divide $2^{20} - 1$. Clearly we have $2 \equiv 2 ~(mod ~41) $. By property $6.$ of Theorem , we have  $2^{2} \equiv 4 ~(mod ~41)$. On the same line we have $2^{3} \equiv 8 ~(mod ~41)$. Similarly,  $2^{4} \equiv 16 ~(mod ~41)$ and $2^{5} \equiv 32 ~(mod ~41)$. But $32 \equiv -9 ~(mod ~41)$. Therefore $2^{5} \equiv -9 ~(mod ~41)$. Hence $2^{5} \cdot 2^{5} \equiv (-9) \cdot (-9) ~(mod ~41)$, i.e. $2^{10} \equiv 81 ~(mod ~41)$. But $81 \equiv -1 ~(mod ~41) $, so $2^{10} \equiv -1 ~(mod ~41)$. Again, we have  $2^{10} \cdot 2^{10} \equiv (-1) \cdot (-1) ~(mod ~41)$, i.e. $2^{20} \equiv 1 ~(mod ~41)$. Hence $41$ divide $2^{20} - 1$.

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

Theorem:   For given any integers $a $ and $b$, $a \equiv b ~(mod ~n) $ if and only if $a$ and $b$ leave the same nonnegative remainder when  divided by $n$. Proof: Firstly, we suppose that  $a \equiv b ~(mod ~n)$ and we will show that $a$ and $b$ leave the same nonnegative remainder when divided by $n$. Since  $a \equiv b ~(mod ~n)$, we have $a = b + k \cdot n$ for some integer $k$. When we divide $b$ by $n$,  $ b$ leaves a certain remainder say $r$; that is,  $b = q \cdot n + r$, where $0 \leq r < n$. We put $b = q \cdot n + r$ in $a = b + k \cdot n$.  Therefore, $a =  b + k \cdot n = (q \cdot n + r) + k \cdot n = (q + k) \cdot n + r$ that is  $a$ has the same remainder as $b$, when we divide $a$ by $n$.  Conversely, suppose that $a$ and $b$ leave the same nonnegative remainder when divided by $n$. So  we can write $a = q_{1} \cdot n + r$ and $b = q_2 \cdot n + r$, with the  same remainder $0 \leq r < n$. Then $a...

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

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

  Theorem:  There is an infinite number of primes.  Proof :  Suppose on the contrary that there are only finite number of primes. Let $p_{1} = 2, p_2 = 3, p_3 = 5, p_4 = 7, \cdots $ be  the primes in ascending order, and suppose that there is a last prime, called $p_n$· Now consider the positive integer $P = (p_{1} \cdot p_2 ~ \cdots ~ p_n)+ 1$. Since $P > 1$, by Theorem , $P$ is  divisible by some prime $p$. But $p_{1}, ~p_2, ~ p_3, ~\cdots~, p_n $ are the only prime numbers, so that $p$ must be equal to one of $p_{1}, ~p_2, ~ p_3, ~\cdots~, p_n $ and hence $p ~|~  p_{1} \cdot p_2 ~ \cdots ~ p_n$· Since $p ~|~  p_{1} \cdot p_2 ~ \cdots ~ p_n$ and $p ~|~ P$, we will get $p ~|~ (p_{1} \cdot p_2 ~ \cdots ~ p_n) - P$ i.e. $p ~|~ 1$. Since the only positive divisor of the integer $1$ is $1$ itself so we will get a contradiction to  $p > 1$. Hence there are  infinite number of primes.

Theorem:  The number $\sqrt{2}$ is an irrational.  Proof:   Suppose on the contrary that $\sqrt{2}$ is rational number.   Therefore there exist integers $a$ and $b$ such that $\sqrt{2} = \frac{a}{b}$ with $gcd(a, b) = 1$. By Theorem ,  there must exist integers $r$ and $s$ such that $ ar + bs = 1$. Hence $ \sqrt{2} = \sqrt{2}~ (ar + bs) = \sqrt{2} ar + \sqrt{2} bs =  2br +as $. This show that $\sqrt{2}$ is an integer, which is absurd. Therefore  The number $\sqrt{2}$ is an irrational. 

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

Corollary:  If $p$ is a prime and $p ~|~ a_{1} \cdot a_2 ~\cdots~ a_n$, then $p ~|~ a_k$ for some $k$, where $1 \leq k \leq n$. Proof:  Suppose that $p$ is a prime and $p ~|~ a_{1} \cdot a_2 ~\cdots~ a_n$, then by Theorem , $p ~|~ a_{1}$ or $p ~|~ a_2 \cdot a_3 ~\cdots~ a_n$. If $p ~|~ a_{1}$, then we are done. If $p \nmid a_{1}$, then $p ~|~ a_2 \cdot a_3 ~\cdots~ a_n$. We use Theorem , to $p ~|~ a_2 \cdot a_3 ~\cdots~ a_n$. So we will get either $p ~|~ a_2$ or $p ~|~ a_3 \cdot a_4 ~\cdots~ a_n$. If $p ~|~ a_2$, then we are done. If $p \nmid a_2$, then $p ~|~ a_3 \cdot a_4 ~\cdots~ a_n$. We will make use of Theorem   again and again. Since $n$ is finite, use of Theorem  ,  will stop after finitely many times. So we will get  $p ~|~ a_k$ for some $k$, where $1 \leq k \leq n$. Corollary:  If $p, q_{1}, q_2, ~\cdots~ q_n$ all are primes and $p ~|~ q_{1} \cdot q_2 ~\cdots~ q_n$, then $p = q_k$ for some $k$, where $1 \leq k \leq n$. Proof:   We w...