the natural numbers as referred to by the ancient Greeks. As a student of Abstract or Modern Algebra I find it interesting that most proofs in that field are based on number theoretic arguments. It is customary to apply the term Diophantine equation to any equation in one or more unknowns which is to be solved in the integers.
The mathematician Diophantus lived in Alexandria sometime around 250 A.D.. Diophantus's reputation rests on his great work
y = y_{0} - (a/d)t
for varying integers t.
56x + 72 y = 40
******************* THEOREM: Given integers a and b, not both zero, there exist integers x and y such that a and b may be described as the smallest integer of the form ax + by.
For our example, to find a particular solution in
The first step is: q is an integer and _{1}r is a remainder._{1}
72 = 1
Accordingly: 8 = gcd (56, 72) This is based on:
******************* From the theorem:The Diophantine equation ax + by = c admits a solution if and only if d|c, where d = gcd (a, b)[Proof of this statement lies below.]
Therefore, the last remainder of our example, our greatest common divisor -- 8 -- must divide Backtracking the Euclidean Algorithm, we start with the next to last of the displayed equations above and eliminate remainders. There are only three, so we have:
8 = 56 - 3
40 = 5
y = -15 - 7t --- [ y = y]
_{0} - (a/d)t(for varying integers t) ************************ Proof: There are integers r and s for which a = dr and b = ds. If a solution of ax + by = c exists, so that
[ax_{0} + by_{0} = c] for suitable x_{0} and y_{0}, thenc = ax which simply says that d|c.
d = ax
c = dt = (ax _{0} and y = ty_{0} as a particular solution.
************************ |