Linear-Diophantine-Equations.pptx

Linear Algebra

1. Linear Diophantine Equations By: MARY HARLENE BANATE CHRISTY MAE JOY D. DOLFO MATH 413

2. Diophantus of alexandria Biography - (Born c. AD 200- c. 214; died c. AD 284- c. 298) was a Greek Mathematician , who was the author of a series of books called Arithmetica , many of which are now lost. His texts deal with solving algebraic equations.

3. Biography Title page of the original 1621 edition of the latin translation by Claude Gaspard Bachet de Mezziriac of Diophantus Arithmetica Diophantine equations, Diophantine geometry, and Diophantine approximations are subareas of Number Theory that are named after him.

4. What is Linear Diophantine Equation? A Diophantine Equation is a polynomial equation whose solutions are restricted to integers. A Linear Diophantine Equation is a first-degree equation of this type. Diophantine equations are important when a problem requires a solution in whole amounts. We can write ax + by = c where a, b, c ∈ Z

5. Method for computing the initial solution to a Linear Diophantine Equation in Two Variables Given an equation ax + by = c Use the Euclidean algorithm to compute ( a,b )=d, taking care to record all steps. Determine if d | n. If not, then there are no solutions.

6. Method for computing the initial solution to a Linear Diophantine Equation in Two Variables

7. Theorem Let a,b , and c be integers with a and b not both zero. The linear diophantine equation ax + by = c has a solution if and only if d =(a, b) divides c. Proof Suppose that x 0 and y 0 is a solution. Then ax 0 + by 0 = c. Since d|a and d|b , we get that d|ax 0 + by 0 and d|c .

8. 6x+9y=113 a=6 b=9 c=113 Using Euclidean Algorithm 9 = 6(1) + 3 6 = 3(2) + 0 CDG(6,9)=3 3 does not divide 113 ∴has no solution 10x+15y=33 a=10 b=15 c=33 Using Euclidean Algorithm 15 = 10(1) + 5 10 = 5(2) + 0 GCD(10,15)=5 5 does not divide 33 ∴has no solution Example 1 Example 2

9. 54x+21y=3 Using Euclidean Algorithm 54 = 21(2) +12 21 = 12(1) +9 12 = 9(1) +3 9 = 3(3) +0 CDG(54,21)=3 3 divides 3 ∴has many solution Example 3 3 = 12 – 9 3 = 12 – (21 -12) = 12 – 21 + 12 3 = 12(2) – 21 3 = [54 – 21(2)] (2) – 21 3 = 54(2) – 21(4) – 21 Factor +21 3 = 54(2) + 21(-5) c = ax + by ∴ x = 2 y = -5

10. 18x + 5y = 48 Using Euclidean Algorithm 18 = 5(3) + 3 5 = 3(1) + 2 3 = 2(1) + 1 2 = 2(1) + 0 CDG(18,5)=1 1 divides 48 ∴has many solution 1 = 3 – 2 1 = 3 – (5 -3) = 3 – 5 + 3 1 = 3(2) – 5 1 = [18 – 5(3)] (2) – 5 1 = 18(2) – 5(6) – 5 Factor +5 1 = 18(2) + 5(-7) c = ax + by ∴ x = 2 y = -7 Example 4

11. Practice 16x + 10y = 17 Using Euclidean Algorithm 16 = 10(1) + 6 10 = 6(1) + 4 6 = 4(1) + 2 4 = 2(2) + 0 CDG(16,10)=2 2 does not divide 17 ∴has no solution 20x + 6y = 55 Using Euclidean Algorithm 20 = 6(3) + 2 6 = 2(3) + 0 CDG(20,6)=2 2 does not divide 55 ∴has no solution

12. 45x + 33y = 9 Using Euclidean Algorithm 45 = 33(1) + 12 33 = 12(2) + 9 12 = 9(1) + 3 9 = 3(3) + 0 CDG(45,33)=3 3 divides 9 ∴has many solution 3 = 12 – 9 3 = 12 – [33 – 12(2)] = 12 – 33 + 12(2) Factor 12 3 = 12(3) – 33 3 = (45 – 33)(3) – 33 = 45(3) – 33(3) - 33 Factor +33 3 = 45(3) + 33(-4) c = ax + by ∴ x = 3 y = -4 Practice

13. 15x + 11y = 3 Using Euclidean Algorithm 15 = 11(1) + 4 11 = 4(2) + 3 4 = 3(1) + 1 3 = 1(3) + 0 CDG(15,11)=1 1 divides 3 ∴has many solution 1 = 4 – 3 1 = 4 – [11 –4(2)] = 4 – 11 + 4(2) Factor 4 1 = 4(3) – 11 1 = (15 – 11)(3) – 11 = 15(3) – 11(3) - 11 Factor +11 1 = 15(3) + 11(-4) c = ax + by ∴ x = 3 y = -4 Practice