Mathematics

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