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. 

    Srinivasa Ramanujan   (22 December 1887 – 26 April 1920) (Image Source: https://en.wikipedia.org/wiki/Srinivasa_Ramanujan ) Early Life and Education: Ramanujan was born into a distinguished Brahmin family in the vibrant town of Erode, Tamil Nadu. His father, K. Srinivasa Iyengar, diligently served as a clerk in a bustling cloth shop, while his mother, Komalatammal, devoted herself to homemaking and captivated the community with her melodious voice during temple hymns. As a child, he made the significant move to Kumbakonam, a city rich in culture and history, which would play a crucial role in nurturing his exceptional talent and intellect. Srinivasa Ramanujan exhibited extraordinary mathematical prowess from a young age, making him a standout figure in the field. By age 10, he was already excelling in arithmetic, and by the age of 12, he had not only mastered trigonometry but also began uncovering mathematical formulas on his own. This early brilliance under...

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