Equations of ax + by = d, and (a , b) = d

Sometimes we may be interested in solving equations in the form of ax + by = d, where:

(1)
\begin{align} x, y \in \mathbb{Z} \end{align}

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)
\begin{align} 96 = 27q + r \\ 96 = 27(3) + 15\\ 27 = 15q_1 + r_1 \\ 27 = 15(1) + 12 \\ 15 = 12q_2 + r_2 \\ 15 = 12(1) + 3 \\ 12 = 3q_3 + r_3\\ 12 = 3(4) + 0 \\ \quad (96, 27) = (27 , 15) = (15, 12) = (12 , 3) = 3 \end{align}

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)
\begin{align} 3 = 15 + 12(-1) \\ 3 = 15 + (27 - 15)(-1) \\ 3 = 15 + (27)(-1) + (-15)(-1) \\ 3 = 2(15) + (27)(-1) \\ 3 = 2(96 - 3(27)) + (27)(-1) \\ 3 = 2(96) -6(27) + (27)(-1) \\ 3 = 96(2) + 27(-7) \end{align}

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)
\begin{align} 96(2) + 27(-7) = 3 \\ 192 + (-189) = 3 \\ 192 - 189 = 3 \\ 3 = 3 \end{align}

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:
(5)
\begin{equation} dx + ay = 1 \end{equation}
  • Since b is an integer, we can multiply both sides of the equation to obtain:
(6)
\begin{equation} bdx + bay = b \end{equation}
  • But we also know that d | bdx, and we were given that d | ab, so then d | bay. Hence:
(7)
\begin{equation} d | (bdx + bay) \end{equation}
  • 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:
(8)
\begin{equation} c | (ax + by) \end{equation}
  • 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 q1 and q2 such that:
(9)
\begin{align} aq_1 = m \\ bq_2 = m \end{align}
  • Thus by this equality we can obtain:
(10)
\begin{equation} aq_1 = bq_2 \end{equation}
  • Notice that a | bq2, but also (a , b) = 1 (from this corollary). Hence, from corollary 1, we obtain that a | q2. Hence, there exists some integer r such ar = q2:
(11)
\begin{equation} ar = q_2 \end{equation}
  • By substitution of q2, we obtain:
(12)
\begin{align} ar = m/b \\ abr = m \end{align}
  • Thus it follows that ab | m, since ab | abr.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License