Linear Diophantine Equations

 



Linear Diophantine equations are equations of the form:

$$ax+by=c$$

where $a, b, c, x,$ and $y$ are integers, and $a, b$ are not both zero.
These equations are named after the ancient Greek mathematician Diophantus, who studied them extensively. The solutions to these equations are integers $x$ and $y$ that satisfy the equation.

Linear Diophantine equations have applications in various fields, including number theory, cryptography, and optimization problems.

A Diophantine equation is a polynomial equation with 2 or more integer unknowns.

A Linear Diophantine equation (LDE) is an equation with 2 or more integer unknowns and the integer unknowns are each to at most degree of 1.

Linear Diophantine equation in two variables takes the form of $𝑎𝑥+𝑏𝑦=𝑐$, where $𝑥,𝑦∈ℤ$ and $a, b, c$ are integer constants. $x$ and $y$ are unknown variables.

A Homogeneous Linear Diophantine equation (HLDE) is $𝑎𝑥+𝑏𝑦=0$,$x,y∈Z$. Note that $x=0$ and $𝑦=0$is a solution, called the trivial solution for this equation.

Here's how you can solve Linear Diophantine Equations:

Check for Solutions: First, you need to determine if there are any solutions at all. This involves checking if $c$ is divisible by the greatest common divisor (GCD) of $a$ and $b$. If it is, then solutions are possible; otherwise, there are no integer solutions.

Find One Solution: You can use the Extended Euclidean Algorithm to find one solution to the equation. The algorithm gives you values of $x$ and $y$ such that $ax + by = \text{GCD}(a, b)$

Find All Solutions: Once you have one solution, you can find all solutions by adding integer multiples of $b/\text{GCD}(a, b)$ to the $x$ value and subtracting integer multiples of $a/\text{GCD}(a, b)$ from the $y$ value. This will give you all possible solutions.

  • The general solution can be expressed as: $x = x_0 + \frac{b}{\gcd(a, b)}t$, $y = y_0 - \frac{a}{\gcd(a, b)}t$.
  • Here, $(x_0) and (y_0)$ are the initial solutions, and $(t)$ is an integer parameter.

Special Cases:If $a$ and $b$ are relatively prime (i.e., their GCD is 1), then there are infinitely many solutions.If $c$ is not divisible by the GCD of $a$ and $b$, then there are no integer solutions.

So follow these steps to find the solutions of linear Diophantine equation $ax+by=c$

  • Calculate $d=gcd(a,b)$ using the Euclid's Algorithm
  • Check whether $d$ divides $c$:if it does not, there are no solutions, stop here.If it does write $c=de$
  • If $d|c$ , find integers $u$ and $v$ such that $au+bu=d$, then $x_0=ue,y_0=ve$ is a particular solution of $ax+by=c$

Now find the general solution $x,y$ of the equation using the formauls

$$x=x_0+\frac{b}{d}. t\: ,t \in \mathbb{Z}$$ $$y_0=y_0-\frac{a}{d}.t \: ,t \in \mathbb{Z}$$

Let's illustrate with an example:

Example: Solve the linear Diophantine equation $15x+25y=10$

Check for Solutions: The GCD of 15 and 25 is 5. Since 10 is divisible by 5, solutions are possible.

Find One Solution: 

Using the Extended Euclidean Algorithm, we find that $15 \times (-1) + 25 \times (1) = 10$. So, one solution is $x=-1$ and $y=1$ 

Find All Solutions: 

Adding integer multiples of $25/5=5$ to -1 and subtracting integer multiples of  $15/5=3$ from 1, we get all possible solutions. So, the general solution is $x=-1+5t$ and $y=1−3t$, where $t$ is an integer

Homogeneous Linear Diophantine Equation

Let $𝑎𝑥+𝑏𝑦=0,𝑥,𝑦∈ℤ$ be a homogeneous linear Diophantine equation.
If $gcd(𝑎,𝑏)=𝑑$ then the complete family of solutions to the above equation is
$𝑥=\frac{𝑏}{𝑑}t$, and $𝑦=\frac{−𝑎}{𝑑}t,t∈Z.$

Example:Solve the Homogeneous linear Diophantine equation

$6𝑥+9𝑦=0,𝑥,𝑦∈ℤ$

Solution:
Note that GCD of 6 and 9 is 3. Hence the solutions are
$𝑥=\frac{9}{3}t$ and $𝑦=\frac{−6}{3}t, t∈Z$.

Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident
Read more

Quadratic Residues-Legendre and Jacobi Symbols

Image
Quadratic Congruence   There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them. We know that the solution of the quadratic equation can be found by  $$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$. We can write the equation in the form $$(2ax+b)^2=b^2-4ac$$ If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$. If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none. Example: Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$ given $a=1, b=−3$ and $c=2,$ we have: $b^2−4ac=(−3)^2−4(1)(2)=9−8=1$ So, $b^2−4ac=1.$ Now, we ne
Read more