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 $x = x_{0} + (\frac{b}{d}) \cdot t$,  $y = y_{0} - (\frac{a}{d}) \cdot t$, where $t$ is an arbitrary integer.


Proof:  Suppose that the linear  equation $ax +by = c$ has a integers solution. We will show that $d = gcd(a,b)$  divides $c$. Let $x_{0}$ and $y_{0}$ be a integer solution of equation $ax +by = c$, so we get $a x_{0} + b y_{0} = c$.  Since $d = gcd(a,b)$, there exist integers $r$ and $s$ such that $a =dr$ and $b =ds$. Put $a =dr$ and $b =ds$ in  equation $a x_{0} + b y_{0} = c$. Therefore $c = a x_{0} + b y_{0} = dr x_{0} + ds y_{0} = d \cdot (r x_{0} + s y_{0})$. This implies $d = gcd(a,b)$ divides $c$.  

Conversely, suppose that $d = gcd(a,b)$  divides $c$. Therefore there exists an integer $t$ such that $c =dt$. We will show that the linear  equation $ax +by = c$ has a integers solution. Since $d$ is the $gcd(a,b)$, by Theorem, we can find integers $x'$ and $y'$ such that $d = ax' + by'$. Multiply equation $d = ax' + by'$  by $t$, we get $c =d \cdot  t = (ax' + by')\cdot t = a  \cdot (tx') + b  \cdot (ty')$. Therefore linear  equation $ax +by = c$ has $x = tx'$ and $y = ty'$ as a particular integers solution.

Now, we will the prove moreover part of this theorem. Let $x_{0}, ~y_{0}$ be a particular known integer solution of the equation $ax +by = c$. If $x_{1}, ~y_{1}$ is any other integer solution of the equation $ax + by = c$, then $a x_{0} + b y_{0} = a x_{1} + b y_{1} = c$. This gives $a \cdot (x_{1} - x_{0}) = b \cdot (y_{0} -y _{1})$. By Corollary, there exist relatively prime integers $r$ and $s$ such that $ a = d \cdot  r,~ b = d \cdot s$. we put $ a = d \cdot r,~ b = d \cdot s$ in $a \cdot (x_{1} - x_{0}) = b \cdot (y_{0} -y _{1})$ and cancel the common factor $d$. We will get  $r \cdot (x_{1} - x_{0}) = s \cdot (y_{0} -y _{1})$.  In this situation, $r ~|~s \cdot (y_{0} -y _{1})$ with $gcd(r,s) = 1$. By Euclid's Lemma, $r ~|~ (y_{0} - y _{1})$ i.e. $y_{0} - y _{1} = r \cdot t$ for some integer $t$. we put $y_{0} - y _{1} = r \cdot t$ in $r ~(x_{1} - x_{0}) = s \cdot (y_{0} -y _{1})$ and canceling $r$ from both side we will get $x_{1} - x_{0} = s \cdot t$. Therefore  $x_{1} = x_{0} + (\frac{b}{d}) \cdot t$,  $y_{1} = y_{0} - (\frac{a}{d}) \cdot t$ .Note that values of $x_{1}, y_{1}$ satisfies given Diophantine equation regardless value of $t$. Consider $a x_{1} + b y_{1} = a ~[x_{0} + (\frac{b}{d}) ~t] + b~ [y_{0} - (\frac{a}{d}) ~t]  = (ax_{0} + by_{0}) + (\frac{ab}{d} - \frac{ab}{d} ) ~ t  = c $. Thus, there are an infinite number of solutions of the given equation, one for each value of $t$.


Remark:  The linear  equation $ax +by = c$ is a Diophantine equation if and only if $d$ divides $c$, where $d = gcd(a,b)$.

Popular posts from this blog

Definition of divisibility and Theorem on divisibility

  Definition: An integer $b$ is said to be divisible by an integer $a \not = 0$, if there exists some integer $c$ such that $ b = a \cdot c$. An integer $b$ is  divisible by an integer $a \not = 0$, is denoted by $a ~|~ b$.  We write $a \nmid b$ to indicate that $b$  is not divisible by $a$. Theorem: For integers $a, ~b, ~c$ the following hold: $1.$ $a ~|~ 0, ~ 1 ~|~ a, ~ a ~|~ a $. $2.$  $ a ~|~ 1 $ if and only if $a =  1$ or $a = -1$. $3.$  If $a ~|~ b$ and $c ~|~ d$, then $a \cdot c ~|~ b \cdot d$. $4.$   If $a ~|~ b$ and $b ~|~ c$, then $a ~|~ c$. $5.$  If $a ~|~ b$ and $b ~|~ a$ if and only if $a =  b$ or $a = -b$. $6.$  If $a ~|~ b$ and $b \not = 0$, then $|a| \leq |b|$. $7.$  If $a ~|~ b$ and $a ~|~ c$, then $a~ |~ (b \cdot x + c \cdot y)$ for arbitrary integers $x$ and $y$. Proof: $1.$ For any integer $a$, we can write $0 = a \cdot 0$, $a = 1 \cdot a$ and $a = a \cdot 1$. Theref...
Read more

The Division Algorithm / Prove that given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$.

Image
State and prove Division Algorithm theorem.  Theorem:  Given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$. Proof : Firstly, we will show that the set $S = \{a - x \cdot b \;|\; x \in \mathbb{Z}$ and $  a -x \cdot b \geq 0\}$ is nonempty.  For this purpose, we have to find value of $x$ such that $a -x \cdot b \geq 0$. Given that integer $b > 0$, i.e. $b \geq 1$. Multiply $b \geq 1$ by $|a|$, we get $|a|\cdot b \geq |a|$ and so $a - ( - |a|) \cdot b = a + |a| \cdot b \geq a + |a| \geq 0$. If we take $x = |a|$, then, $a -x \cdot b \in S$. This show that $S$ is nonempty subset of nonnegative integers. By the Well-Ordering Principle (for more details see  Well-Ordering Principle  ) , set $S$ contains a least integer; say it $r$. Since $r \in S$, there exists an i...
Read more

Define Greatest Common Divisor and Prove that if $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$.

Image
Definition: Let $a$ and $b$ be any integers, with at least one of them is not zero. The greatest common divisor of $a$ and $b$, denoted by $gcd(a, b)$, is the positive integer $d$ satisfying the following: $1.$  $d ~|~ a$ and $d ~|~ b$. $2.$ If $c ~|~ a$ and $c ~|~ b$, then $c \leq d$. Theorem:  If $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$. Proof:   Let  $a$ and $b$ be any integers, not both of them are zero. Consider the set $S = \{a \cdot u + b \cdot  v \;|\; a \cdot  u + b \cdot  v > 0$ and $ u, v \in \mathbb{Z}\}$, that is  $S$ is the set of all positive linear combinations of $a$ and $b$. Firstly, we will show  that $S$ is nonempty set. We have taken integers $a$ and $b$ such that not both of them are zero. Without loss of generality, suppose that $a \not = 0$. Then the integer $|a| = a \cdot u + b \cdot 0 \in S$ for the v...
Read more