Mathematics

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

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

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

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

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

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

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

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