Table of Contents

Sometimes we may be interested in solving equations in the form of ax + by = d, where:
(1)Namely, for some function ax + by + d, we want to find integer solutions for the variables x and y. For example, we may want to see if there exists an integers x and y such that 12x + 59y = 2. Such equations are know as Diophantine equations.
It turns out that there is an important property relating solutions to equations in the form of ax + by = d.
Theorem: If (a , b) = d, then there exists integers x and y such that ax + by = d.
Example 1:
Determine integer solutions to the equation: 27x  96y = 3.
First let's determine if (27, 96) = 3. We can accomplish this by the Euclidean algorithm.
(2)Therefore, it is true that (27 , 96) = 3. We can now back substitute to find an equation in the form of ax + by = d.
(3)Hence, it should be rather obvious that the solution x = 2, and y = 7 satisfies the equation 96x + 27y = 3. We can verify this:
(4)Corollaries of this Theorem
Corollary 1: If d  ab and (d , a) = 1, then d  b.
 Proof: Notice that since (d , a) = 1, then there exists integers x and y such that we obtain the equation:
 Since b is an integer, we can multiply both sides of the equation to obtain:
 But we also know that d  bdx, and we were given that d  ab, so then d  bay. Hence:
 Therefore, d  b, since d divides the lefthand side of the equation.
Corollary 2: If (a , b) = d, c a, and c  b, then c  d.
 Proof: Because (a , b) = d, then there exists integers x and y such that ax + by = d (by the theorem on this page). If c  a and c  b, then it follows that:
 Which also means that c  d since c divides the lefthand side of the equation.
Corollary 3: If (a , b) = 1, a  m, b  m, then ab  m.
 Proof: Since a  m and b  m, there exists integers q_{1} and q_{2} such that:
 Thus by this equality we can obtain:
 Notice that a  bq_{2}, but also (a , b) = 1 (from this corollary). Hence, from corollary 1, we obtain that a  q_{2}. Hence, there exists some integer r such ar = q_{2}:
 By substitution of q_{2}, we obtain:
 Thus it follows that ab  m, since ab  abr.