Javascript required
Skip to content Skip to sidebar Skip to footer

Finding Minimal Solutions of Diophantine Equations

Returning to the example in the introduction...

How many ways are there to make $ 2.00 \$2.00 from only nickels and quarters?


As before, the goal is to find the non-negative integer solutions of

5 n + 25 q = 200. 5n+25q=200.

Note that there is a common factor, 5. 5. Dividing out this common factor gives

n + 5 q = 40. n+5q=40.

The smallest possible value for either variable is 0 0 , but n n must be a multiple of 5 5 . There are 9 9 non-negative multiples of 5 5 that are less than or equal to 40 40 (including 0 0 ). Therefore, there are 9 \color{#D61F06} 9 ways to make $ 2.00 \$2.00 from only nickels and quarters. The ordered pairs ( n , q ) (n,q) are listed below:

( 0 , 8 ) , ( 5 , 7 ) , ( 10 , 6 ) , ( 15 , 5 ) , ( 20 , 4 ) , ( 25 , 3 ) , ( 30 , 2 ) , ( 35 , 1 ) , ( 40 , 0 ) . \begin{array}{c}&(0,8), &(5,7), &(10,6), &(15,5), &(20,4), &(25,3), &(30,2), &(35,1), &(40,0).\ _\square \end{array}

The solutions to a Diophantine equation aren't always simple multiples.

Travis is purchasing beverages for an upcoming party. He has $68 to spend. He can purchase packs of cans for $12, or smaller packs of bottles for $8.00. How many ways are there for him to purchase beverages if he spends all of his money?


Let c c be the number of packs of cans he purchases and let b b be the number of packs of bottles he purchases. The goal is to find the non-negative solutions to

12 c + 8 b = 68. 12c+8b=68.

First note that there is a common factor, 4 4 . Dividing out this common factor gives

3 c + 2 b = 17. 3c+2b=17.

17 17 is not divisible by 3 3 nor 2 2 , so he must purchase some combination of cans and bottles. Begin by finding a solution in which he purchases the maximum number of cans. He could purchase at most 5 5 packs of cans. This gives

15 + 2 b = 17 , 15+2b=17,

which leaves him with just enough money to purchase 1 1 pack of bottles. Now consider how this solution could be altered to find more solutions. Consider if he only bought 4 4 packs of cans:

12 + 2 b = 17. 12+2b=17.

This equation gives no integer solution for b b , so this is not possible. One can observe that the number of packs of cans must decrease in increments of 2 2 . Meanwhile, the number of packs of bottles will increase in increments of 3. 3. The ordered-pair solutions ( c , b ) (c,b) are listed below:

( 5 , 1 ) , ( 3 , 4 ) , ( 1 , 7 ) . \begin{array}{ccc} (5,1), & (3,4), & (1,7). \end{array}

Therefore, if Travis spends all his money, there are 3 \color{#D61F06} 3 ways he could purchase beverages for the party. _\square

In many practical problems, solutions will be limited to non-negative integers. However, this is not necessarily true for all problems.

Find how many integer solutions there are to the following equation subject to x , y [ 20 , 20 ] : x,y\in[-20,20]:

3 x + 5 y = 11 ? 3x+5y=11?


One can see that the ordered pair ( 2 , 1 ) (2,1) is a solution. Then, the x x value must increase/decrease by a multiple of 5 , 5, and the y y value will have a corresponding decrease/increase by a multiple of 3. 3. Since the x x value increases/decreases faster, it is more constrained by the restriction that x , y [ 20 , 20 ] . x,y\in [-20,20]. The maximum value of x x gives an ordered-pair solution of ( 17 , 8 ) . (17, -8). The minimum value of x x gives an ordered-pair solution of ( 18 , 13 ) . (-18,13). In total, there are 17 ( 18 ) 5 + 1 = 8 \frac{17-(-18)}{5}+1=\color{#D61F06} 8 solutions subject to x , y [ 20 , 20 ] . x,y\in[-20,20]. _\square

Jack, Charlie, and Andrew went on an egg hunt today, each of them carrying one basket. 300 eggs were hidden at the beginning of the day. At the end of the day, the numbers of eggs in each of the boys' baskets are three consecutive integers.

In how many ways could this happen?

Clarification: Order doesn't matter. For example, in the order of Charlie, Andrew, and Jack, ( 3 , 2 , 1 ) (3,2,1) and ( 2 , 3 , 1 ) (2,3,1) both count as one way.

Not all linear Diophantine equations have a solution.

Find the integer solutions to the equation

12 x + 21 y = 80. 12x+21y=80.


There is no common factor for the entire equation, but the left side of the equation has a common factor of 3 : 3:

3 ( 4 x + 7 y ) = 80. 3(4x+7y)=80.

Recall that x x and y y must be integers. This means that ( 4 x + 7 y ) (4x+7y) is also an integer. However, the equation implies that 4 x + 7 y = 80 3 . 4x+7y=\frac{80}{3}. By contradiction, there are no integer solutions to the equation. _\square

You may have observed from the examples above that finding solutions to linear Diophantine equations involves finding an initial solution, and then altering that solution in some way to find the remaining solutions. The process of finding this initial solution isn't always as straightforward as the examples above. Fortunately, there is a formal process to finding an initial solution.

First, it is important to recognize when solutions exist. Recall the previous example in which there were no solutions. There was a common factor between the coefficients of the variables, but the constant term was not divisible by this factor. This observation is generalized with the Bézout's identity:

Bézout's Identity:

Let a a and b b be non-zero integers and let d = gcd ( a , b ) . d=\gcd(a,b). Then there exist integers x x and y y that satisfy

a x + b y = d . ax+by=d.

Furthermore, there exist integers x x and y y that satisfy

a x + b y = n ax+by=n

if and only if d n . d\mid n.

One can determine if solutions exist or not by calculating the GCD of the coefficients of the variables, and then determining if the constant term can be divided by that GCD.

Find all integers solutions to the equation

14 x + 91 y = 53. 14x+91y=53.


First, calculate gcd ( 14 , 91 ) = 7. \gcd(14,91)=7. Then, observe that 7 53. 7\nmid 53. Therefore, by Bézout's Identity, there are no integer solutions to the equation. _\square

If solutions do exist, then there is an efficient method to find an initial solution. The Euclidean algorithm gives both the GCD of the coefficients and an initial solution.

Method for computing the initial solution to a linear Diophantine equation in 2 variables

Given an equation a x + b y = n : ax+by=n:

  • Use the Euclidean algorithm to compute gcd ( a , b ) = d \gcd(a,b)=d , taking care to record all steps.
  • Determine if d n . d\mid n. If not, then there are no solutions.
  • Reformat the equations from the Euclidean algorithm.
  • Using substitution, go through the steps of the Euclidean algorithm to find a solution to the equation a x i + b y i = d . ax_i+by_i=d.
  • The initial solution to the equation a x + b y = n ax+by=n is the ordered pair ( x i n d , y i n d ) . \left(x_i\cdot \frac{n}{d},\ y_i\cdot \frac{n}{d}\right).

Find an initial integer solution to the equation

141 x + 34 y = 30. 141x+34y=30.


Using the Euclidean algorithm, we have

141 = 4 ( 34 ) + 5 34 = 6 ( 5 ) + 4 5 = 1 ( 4 ) + 1. \begin{aligned} 141 &= 4(34)+5 \\ 34 &= 6(5)+4 \\ 5 &= 1(4)+\color{#D61F06}{1}. \end{aligned}

Therefore gcd ( 141 , 34 ) = 1. \gcd(141,34)=1. Solutions exist because 1 30. 1\mid 30.

Reformat the equations from the Euclidean algorithm:

5 = 141 4 ( 34 ) 4 = 34 6 ( 5 ) 1 = 5 1 ( 4 ) . \begin{aligned} 5 &=141-4(34) \\ 4 &= 34-6(5) \\ 1 &= 5-1(4). \end{aligned}

Now use substitution to find a solution to the equation 141 x i + 34 y i = 1 : 141x_i+34y_i=1:

1 = 5 1 ( 4 ) 1 = 5 1 [ 34 6 ( 5 ) ] 1 = 7 ( 5 ) 1 ( 34 ) 1 = 7 [ 141 4 ( 34 ) ] 1 ( 34 ) 1 = 7 ( 141 ) 29 ( 34 ) . \begin{aligned} 1 &= 5-1(4) \\ 1 &= 5-1\big[34-6(5)\big] \\ 1 &= 7(5)-1(34) \\ 1 &= 7\big[141-4(34)\big]-1(34) \\ 1 &= 7(141)-29(34). \end{aligned}

This gives x i = 7 x_i=7 and y i = 29 y_i=-29 as a solution to the equation 141 x i + 34 y i = 1 141x_i+34y_i=1 .

Then an initial solution to the equation 141 x + 34 y = 30 141x+34y=30 is

x = 7 30 = 210 y = 29 30 = 870. \begin{aligned} x&=7 \cdot 30\\&=210\\\\ y&=-29 \cdot 30\\&=-870.\ _\square \end{aligned}

In the example above, an initial solution was found to a linear Diophantine equation. This is just one solution of the equation, however. When integer solutions exist to an equation a x + b y = n , ax+by=n, there exist infinitely many solutions.

If ( x , y ) \left(x^*,y^*\right) is an integer solution of the Diophantine equation a x + b y = n , ax + by = n, then all integer solutions to the equation are of the form

( x + m b gcd ( a , b ) , y m a gcd ( a , b ) ) \left(x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)}\right)

for some integer m m .

We have

a ( x + m b gcd ( a , b ) ) + b ( y m a gcd ( a , b ) ) = a x + b y + a b m gcd ( a , b ) a b m gcd ( a , b ) = a x + b y = c , \begin{aligned} a \left( x^* + m \frac{b}{\gcd(a,b)} \right) + b \left( y^* - m \frac{a}{\gcd(a,b)} \right) &= ax^* + by^* + \frac{ a b m}{\gcd(a,b)} - \frac{abm}{\gcd(a,b)} \\ &= ax^* + by^* \\ & = c, \end{aligned}

which shows these are indeed solutions to the Diophantine equation. Now, given any solution ( x , y ) (x, y) , we have

a x + b y = a x + b y a ( x x ) = b ( y y ) a gcd ( a , b ) ( x x ) = b gcd ( a , b ) ( y y ) . \begin{aligned} ax + by &= ax^* + by^* \\ a(x - x^*) &= -b(y - y^*) \\ \frac{a}{\gcd(a,b)} (x - x^*) &= - \frac{b}{\gcd(a,b)} (y-y^*) . \end{aligned}

Since a gcd ( a , b ) \frac{a}{\gcd(a,b)} and b gcd ( a , b ) \frac{b}{\gcd(a,b)} are relatively prime, there exists an integer m m such that x x = m b gcd ( a , b ) x-x^* = m \frac{b}{\gcd(a,b)} and y y = m a gcd ( a , b ) , y-y^* = -m \frac{a}{\gcd(a,b)}, proving the theorem. _\square

Find all integer solutions to the equation

141 x + 34 y = 30. 141x+34y=30.


From before, an initial solution is x = 210 , y = 870. x^*=210,\ y^*=-870.

Then for any integer m , m, a solution is

( x + m b gcd ( a , b ) , y m a gcd ( a , b ) ) = ( 210 + 34 m , 870 141 m ) . \left(x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)}\right) = \left(210+34m,\ -870-141m\right).\ _\square

In some applications, it may be of interest to find the positive (or non-negative) integer solutions of the Diophantine equation a x + b y = c ax + by = c . For these problems, we would like to find the integer values m m such that the solutions

x + m b gcd ( a , b ) , y m a gcd ( a , b ) x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)}

are both positive (or both nonnegative).

Find all integers c c such that the linear Diophantine equation 52 x + 39 y = c 52x + 39y = c has integer solutions, and for any such c , c, find all integer solutions to the equation.


In this example, gcd ( 52 , 39 ) = 13. \gcd(52,39) = 13. Then the linear Diophantine equation has a solution if and only if 13 13 divides c c . Thus, the values c c such that the equation has integer solutions are the multiples of 13 13 . Now, for any such c c , one solution to the Diophantine equation is ( x , y ) = ( c 13 , c 13 ) (x^*,y^*) =\left( \frac{c}{13}, - \frac{c}{13} \right) . Then, the above implies the integer solutions to the equation are

( x , y ) = ( c 13 + 3 m , c 13 4 m ) (x,y) = \left( \frac{c}{13} + 3m, ~ - \frac{c}{13} - 4m \right)

for m m integer. _\square

Find the positive integer solutions of the Diophantine equation 4 x + 7 y = 97 4x + 7y = 97 .


We have gcd ( a , b ) = gcd ( 4 , 7 ) = 1 \gcd(a,b) = \gcd(4,7)=1 and 1 = 4 2 + 7 ( 1 ) 1 = 4 \cdot 2 + 7 \cdot (-1) . Then one solution is x = 2 97 x^* = 2 \cdot 97 and y = ( 1 ) 97 y^* = (-1) \cdot 97 , and all solutions are of the form

( x + m b gcd ( a , b ) , y m a gcd ( a , b ) ) \left( x^* + m \frac{b}{\gcd(a,b)}, ~ y^* - m \frac{a}{\gcd(a,b)} \right) or ( 2 97 + 7 m , 97 4 m ) \left( 2 \cdot 97+ 7m, ~ -97 - 4m \right)

for m m integer. Then we would like to find the integers satisfying 2 97 + 7 m > 0 2 \cdot 97 + 7m > 0 and 97 4 m > 0 -97 - 4m > 0 , or

2 97 7 < m < 97 4 . - \frac{ 2 \cdot 97}{7} < m < - \frac{97}{4} .

The integers m m satisfying this equation are m = 27 , 26 , 25 m=-27, -26, -25 , which gives the solutions ( 5 , 11 ) , ( 12 , 7 ) , (5, 11), (12,7 ), and ( 19 , 3 ) (19,3) . _\square

83 75 n ( m o d 32 ) 83 \equiv 75n \pmod{32}

What is the least possible positive integer n n satisfying the congruence above?

An ice cream shop sells 3 flavored scoops: lime, vanilla, and strawberry. Each customer may choose to buy single, double, or triple scoops, and no one orders repeated flavor on the same cone.

For the single scoop, the lime flavor costs 1 dollar each, vanilla 1.5 dollars each, and strawberry 2 dollars each. For double scoops, each order will get a discount of 31 cents off for any combination. For example, the double scoops of lime and strawberry flavors will cost 1 + 2 0.31 = 2.69 1+2-0.31=2.69 dollars. Finally, for the triple scoops of 3 flavors, it will be discounted to 3.79 dollars.

At the end of the day, 63 lime, 61 vanilla, and 56 strawberry scoops are sold, and the shopkeeper collects 249.75 dollars in total from customers for these sales.

How many customers bought the ice cream? Assume each ice cream is sold to a different person.

Now, consider the linear Diophantine equation in three variables a x + b y + c z = d . ax + by + cz = d. Again by Bézout's Identity, as a a and b b range over all integer values, the set of values a x + b y ax + by is equal to the set of multiples of gcd ( a , b ) . \gcd(a,b). This shows that the Diophantine equation a x + b y + c z = d ax+by+cz=d has integer solutions if and only if gcd ( a , b ) w + c z = d \gcd(a,b)w+cz=d has integer solutions, for a x + b y = gcd ( a , b ) w . ax+by=\gcd(a,b)w. By the above reasoning, the second equation has integer solutions if and only if gcd ( a , b , c ) \gcd(a,b,c) divides d . d.

By continuing this argument, the linear Diophantine equation

a 1 x 1 + a 2 x 2 + + a k x k = d a_1x_1 + a_2x_2 + \cdots + a_kx_k=d

has an integer solution ( x 1 , x 2 , , x k ) (x_1, x_2, \ldots, x_k) if and only if gcd ( a 1 , a 2 , , a k ) \gcd(a_1,a_2, \ldots, a_k) divides d d .

As seen above, a general solution to a linear Diophantine equation with two variables has one integral parameter. In general, if it exists, a solution to an equation with n n variables has n 1 n - 1 integral parameters.

Consider 3 positive integers x , y , x, y, and z z satisfying the following equation: 28 x + 30 y + 31 z = 365 28x+30y+31z=365 .

What is the value of x + y + z ? x+y+z?


First, looking closely at the equation, we can notice that the coefficients are the number of days in the months and the right-hand side of the equation is the number of days in a year.

February is the month with 28 days. There are 4 months in the year with 30 days and 7 months consisting of 31 days.

Hence we get a solution x = 1 , y = 4 x=1, y=4 , and z = 7 z=7 . This would give a solution x + y + z = 12 x+y+z=12 .

But, can we find another positive integer solution? By using trial and error method, we can easily prove that all positive integer solutions of the above equation are ( x , y , z ) = ( 1 , 4 , 7 ) (x,y,z)=(1,4,7) and ( x , y , z ) = ( 2 , 1 , 9 ) (x,y,z)=(2,1,9) . Then, x + y + z x+y+z is always equal to 12 12 .

Surprisingly, we can find the value of x + y + z x+y+z without solving the above equation.

Indeed, because x , y , z x,y,z are positive integers, we have

28 ( x + y + z ) = 365 2 y 3 z 365 2 1 3 1 = 360 x + y + z 360 28 = 12 6 7 31 ( x + y + z ) = 365 + 3 x + y 365 + 3 1 + 1 = 369 x + y + z 369 31 = 11 28 31 . \begin{aligned} 28(x+y+z)=365-2y-3z &\le365-2\cdot1-3\cdot1\\&=360\\\\ x+y+z &\le\dfrac{360}{28}\\&=12\dfrac{6}{7}\\\\ 31(x+y+z)=365+3x+y &\ge365+3\cdot1+1\\&=369\\\\ x+y+z &\ge\dfrac{369}{31}\\&=11\dfrac{28}{31}. \end{aligned}

On the other hand, x + y + z x+y+z is an integer, so x + y + z = 12. x+y+z=12.\ _\square

Consider the integral points ( x , y , z ) (x, y, z) on the plane 35 x + 55 y + 77 z = 1. 35 x + 55 y + 77 z = 1. How many are contained within a cube with side length 30 centered at ( 0 , 0 , 0 ) ? (0, 0, 0)?

If your aim is to solve linear congruences rather than equations, then you should check out the Chinese remainder theorem.

The Chicken McNugget problem is a specific linear Diophantine problem in which the goal is to find the largest integer, N , N, for which no non-negative solution exists to the equation a 1 x 1 + a 2 x 2 + + a n x n = N a_1x_1+a_2x_2+\cdots+a_nx_n=N for some integer coefficients a 1 , a 2 , , a n . a_1, a_2, \cdots, a_n.

The problem of finding the number of ways a set of integers can sum to a certain integer can be solved with a stars and bars approach.

Finding Minimal Solutions of Diophantine Equations

Source: https://brilliant.org/wiki/linear-diophantine-equations-one-equation/