University:
California State University, Northridge
Course:
MATH 105 | Pre-Calculus II
Academic year:

2004
Views:

456

Pages:

1
Author:

Terrance Adams

Diophantine equations. A Diophantine equation is a linear equation with integer coeﬃcients requiring integer solutions. The Diophantine equation ax + by = c has an integer solution if and only if gcd (a, b) divides c. To find one solution to the Diophantine equation ax + by = c follow the steps below. 1. First check that gcd (a, b) | c, to make sure that this equation has in fact integer solutions. a b c 2. Divide the equation by gcd (a, b) to obtain gcd(a,b) x + gcd(a,b) y = gcd(a,b) . We will just b a c 0 0 0 0 write a = gcd(a,b) , b gcd(a,b) , c = gcd(a,b) . So our new equation is a x + b0 y = c0 where gcd (a0 , b0 ) = 1. Note that any solution to ax + by = c is also a solution to a0 x + b0 y = c0 and vice versa. 3. Use the Euclidean algorithm to write the gcd (a0 , b0 ) = 1 as a linear combination of a0 and b0 . Say a0 xo + b0 yo = 1. 4. Finally multiply this last expression by c0 to get a0 (c0 x0 ) + b0 (c0 yo ) = c0 then x = c0 x0 and y = c0 yo is your solution. To get all solutions to the Diophantine equation ax+by = c we actually find all solutions to the equation a0 x + b0 y = c0 as follows. 5. Find one solution (using the four steps above or guessing it). Say x1 and y1 . 6. Then for any integer k we have a0 (x1 + b0 k) + b0 (y1 − a0 k) = c0 . Therefore all solutions to the equation a0 x + b0 y = c0 have the form x = x1 + b0 k y = y1 − a0 k, where k is any integer number.

Diophantine Equations

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock