Posts

Showing posts from December, 2024

Great Indian Mathematician Srinivasa Ramanujan

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

State and Prove Fundamental Theorem of Arithmetic. Prove that 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.

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

Prove that 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$.

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

Definition of prime number. Prove that If $p$ is a prime and $p ~|~ ab$, then $p ~|~ a$ or $p ~|~ b$.

Definition: An integer $p > 1$ is called a prime number, or simply a prime, if its only positive divisors are $1$ and $p$. An integer greater than $1$ that is not a prime is termed composite. Example: We can observe that $2, 3, 5, 7$ etc. are prime numbers whereas $4, 6, 8, 9, 10$ etc. are composite numbers. Theorem: If $p$ is a prime and $p ~|~ ab$, then $p ~|~ a$ or $p ~|~ b$. Proof: If $p ~|~ a$, then we are done. So suppose that $p \nmid a$. Therefore $gcd(p,a) = 1$. Hence by Euclid Lemma , $p ~|~ b$..

If a cock is worth $5$ Rs., a hen $3$ Rs., and three chicks together $1$ Rs. How many cocks, hens and chicks totaling $100$ can be bought for $100$ Rs.

Example:   If a cock is worth $5$ Rs., a hen $3$ Rs., and three chicks together $1$ Rs. How many cocks, hens and chicks totaling $100$ can be bought for $100$ Rs. Proof:  Suppose that $x$ is the number of cocks, $y$ is the number of hen and $z$ is the number of chicks totaling $100$ bought for $100$ Rs. Therefore we will get following equations: $x + y + z = 100$ and  $5x +3y + \dfrac{1}{3} z = 100$ We put $z = 100 - x - y$ in $5x +3y + \dfrac{1}{3} z = 100$. So $5x + 3y + \dfrac{1}{3} (100 - x - y) = 100$ Multiply both side by $3$ $15x +9y +100 - x -y = 300$ $14x +8y = 200$ $7x + 4y = 100$. So we got the linear equation $7x + 4y = 100$. Since $gcd(7,4) = 1$ divides $100$, linear equation $7x + 4y = 100$ is a Diophantine equation and it has a solution. General solution of the equation $7x + 4y = 100$ is $x =4t, ~ y = 25 - 7t$ and hence $z= 75 + 3t$, where $t$ is an arbitrary integer.  Therefore $x = 4,~y = 18 $ and...

Determine all solutions in the integers of Diophantine equation $56x + 72y = 40$.

  Example:   Determine all solutions in the integers of the Diophantine equation $56x + 72y = 40$. Proof:  Firstly, we will find $gcd(56,72)$ using Euclidean Algorithm. We use Euclidean Algorithm and we find that $72 = 56 ~\cdot~ 1 + 16$ $56 = 16 ~\cdot~ 3 + 8$ $16 = 8 ~\cdot~ 2 + 0$ $8$ is the least nonzero remainder obtained in this Algorithm, so $gcd(56,72) = 8$. Since $8 ~ | ~ 40$,  a solution to this equation exists. To obtain  the integer $8$ as a linear combination of $56$ and $72$, we work backward through the previous calculations, as follows:  $8 = 56 - 16 ~\cdot~ 3$ $8 = 56 - (72 - 56 ~\cdot~ 1) ~\cdot~ 3$ $8 = 56 - 72 ~\cdot~ 3 + 56 ~\cdot~ 3$ $8 = 56 ~\cdot~ 4 - 72 ~\cdot~ 3$ $8 = 56 ~\cdot~ 4 + 72 ~\cdot~ (-3)$ We multiply both side of above equation by $5$. Hence we will get  $40 = 56 ~\cdot~ 20 + 72 ~\cdot~ (-15)$ so that $x = 20$ and $ y = - 15$ is a one so...

Diophantine Equation and Theorem on Diophantine Equation. The linear equation $ax +by = c$ has a integers solution if and only if $d$ divides $c$, where $d = gcd(a,b)$.

 Definition:  An equation in one or more variables is said to be a Diophantine equation if it has integer  solution. Example:  Consider the linear equation  $2 x + 8 y = 16$. Linear equation $2 x + 8 y = 16$ has $x = 4, y = 1$ as a integers solution. Therefore $2 x + 8 y = 16$ is a linear Diophantine equation in two variables $x, y$. The Diophantine equation can have a number of solutions. As $x = 8, y = 0$ and $x = 0, y = 2 $ are also integers solution of equation $2 x + 8 y = 16$. Example:  Consider the linear equation  $5 x + 8 y = 16$. Linear equation $5 x + 8 y = 16$ has no integers solution (Why $?$ (We will see in the following Theorem)). Therefore $5 x + 8 y = 16$ is  not a  Diophantine equation. Theorem: The linear  equation $ax +by = c$ has a integers solution if and only if $d$ divides $c$, where $d = gcd(a,b)$.  Moreover, if $x_{0}, ~y_{0}$ is any particular solution of this equation, then all other solutions are...

Use Euclidean Algorithm to find $gcd(42823,6409) $ and find the values of integer $x$ and $y$ satisfying $gcd(42823,6409) = 42823 \cdot x + 6409 \cdot y$.

Example: Use Euclidean Algorithm to find $gcd(42823,6409) $ and find the values of integer $x$ and $y$ satisfying $gcd(42823,6409) = 42823 \cdot x + 6409 \cdot y$. Answer:  To find  $gcd(42823,6409) $ using Euclidean Algorithm. We have to apply Division Algorithm to integers $42823$ and $6409$. Firstly we divide $42823$ by $6409$. When we divide $42823$ by $6409$, we get $q = 6$ (i.e. $6$ is a quotient) and $r = 4369$ (i.e. $4369$ is a remainder). So we get following system of equations in  Euclidean Algorithm. $42823 = 6409~ \cdot ~6 + 4369$ $6409 = 4369 ~\cdot ~1 + 2040$ $4369 = 2040 ~\cdot ~2 + 289$ $2040 = 289 ~\cdot~ 7 + 17$ $289 = 17 ~\cdot ~17 + 0$ $17$ is the last nonzero remainder obtained in this Algorithm, so  $gcd(42823,6409)  = 17$. From the above equations, putting value of remainder (eliminating remainder i.e. $17, ~289,~2040,~ 4369$) and simplifying we can find value of integers $x$ and $y$ such that $gc...

Use the Euclidean Algorithm to find the values of integer $x$ and $y$ satisfying $gcd(24,138) = 24 \cdot x + 138 \cdot y$.

 Example:   Use the Euclidean Algorithm to find the values of integer $x$ and $y$ satisfying $gcd(24,138) = 24 \cdot x + 138 \cdot y$. Solution:  Firstly, we find $gcd(24,138)$ using Euclidean Algorithm. We apply Division Algorithm to integers $24$ and $138$. Firstly, we divide $138$ by $24$. When we divide $138$ by $24$, we get $q = 5$ (i.e. $5$ is a quotient) and $r = 18$ (i.e. $18$ is a remainder). So we get following system of equations in  Euclidean Algorithm. $138 = 24~ \cdot ~5 + 18$  $24 = 18 ~\cdot~ 1 + 6$ $18 = 6 ~\cdot ~3 + 0$ $6$ is the last nonzero remainder obtained in this Algorithm, \linebreak so  $gcd(24, 138)  = 6$. From the above equations, $gcd(24,138) = 6$ can be written as follows $6 = 24 ~-~ 18 ~\cdot~ 1$ we put $18 = 138 ~-~ 24 ~\cdot~ 5$ in above equation, so we get $6 = 24 ~-~ (138 - 24 ~\cdot~ 5) ~\cdot~ 1$ $6 = 24 ~-~ 138  ~\cdot~ 1 + 24 ~\cdot~ 5 $ $6 = 24...

Find greatest common divisor using Euclidean Algorithm. Find $gcd(56,72) $ using Euclidean Algorithm.

Image
Example: Find $gcd(56,72) $ using Euclidean Algorithm. Solution:   To find  $gcd(56,72) $ using Euclidean Algorithm. We have to apply Division Algorithm to integers $56$ and $72$. Firstly we divide $72$ by $56$. When we divide $72$ by $56$, we get $q = 1$ (i.e. $1$ is a quotient) and $r = 16$ (i.e. $16$ is a remainder). So we get following system of equations in  Euclidean Algorithm. $72 = 56~ \cdot ~1 + 16$  $56 = 16 ~\cdot~ 3 + 8$ $16 = 8 ~\cdot ~2 + 0$ $8$ is the last nonzero remainder obtained in this Algorithm, so  $gcd(72, 56)  = 8$.

Euclidean Algorithm: Find Greatest Common Divisor using Euclidean Algorithm.

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

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

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