GMAT Math : Integer solutions

Solving for integer only solutions for a linear equation in the GMAT Quant section can be tricky.  Diophantine equations is an amazing tool to do so amazingly fast.

First, an example to help :

Let an equation be 7x – 8y = 99. How many pairs of integers (xi, yi) are possible such that 7xi – 8yi = 99 and 0 < xi < 100

A. 3

B. 5

C. 11

D. 13

E. 12

The Diophantine solution concept :

For an equation – ax + by = z where a, b, and z are integers, the integer solutions (xn, yn) are represented by :

xn = x1 – nb/gcd(a,b)

yn = y1 + na/gcd(a,b)

where n is any integer and x1 and y1  are any random integer solutions of the equation such that ax1 + by1 = z

Now this might seem a bit hard to interpret – lets solve this with a simple example.

3x + 14y = 20

Even before that, lets figure out what values we need to get to :

xn = x1 – nb/GCD(a,b)

yn = y1 + na/GCD(a,b)

..so we need x1 and y1  (the random solutions) and we need GCD(a,b).  The other values a, b = (3,14) we already have and n is any integer – so no need to figure out its value

Let’s get to GCD (a,b) first.

We use the Euclidean algorithm to determine GCD (3,14)

14 = 3 x 4 + 2

3 = 2 x 1 + 1

..hence GCD (3, 14) = 1

Cool, now we just have to figure out x1 and y1  (the random solutions) such that :

3x1 + 14y1 = 20

One way is to just guess (x1, y1). In this case (2,1) will solve the question.

Now, if a guess solution is not so easy to determine – here is a methodical approach :

Find the solution to:

3(xk) + 14(yk) = GCD (a, b)

An easy way of solving this equation is working backwards from the EUCLIDEAN algorithm:

1= 3 – 2 x 1 (from the last line of the Euclidean algorithm we solved earlier)

1 = 3 – (14 – 3 x 4) x 1

1 = 3 – 14 + 3 x 4

1 = 3 x 5 – 14

So, xk  = 5 and yk = -1

..Notice how we worked backwards (bottom to top) to get the form we wanted i.e

3(xk) + 14(yk) = GCD (a, b)

Good! We know :

1 = 3 x 5 – 14

So, 20 x (1) = 20 x (3 x 5 – 14) = 3 (100) – 14 (20)

20 = 3 (100) – 14 (20)

So, x1 = 100 and y1 = -20

Great, we now know GCD (a,b) and also x1 and y1 (a random solution to the equation). Hence, all potential solutions of 3x + 14y = 20

xn = x1 – nb/GCD(a,b)

yn = y1 + na/GCD(a,b)

xn = 100 – 14n

yn = -20 + 3n

Go ahead! Try any integer value of n and you will have xn and yn as valid integer solutions of 3x + 14y = 20. Readers are encouraged to take a minute to look through the steps we took to get to this point.

Coming to the original question

7x – 8y = 99

Now, GCD (7,8) = 1

i.e., 8 = 7 x 1 + 1

1 = 8 – 7 x 1

Consequently,

99 = 8 (99) – 7 (99)

All the potential solutions can be represented by

xn = x1 – nb/GCD(a,b)

yn = y1 + na/GCD(a,b)

xn = -99 – n (-8) = – 99 + 8n

yn = 99 + n(7) = 7n + 99

Now, 0 < xn < 100

0 < – 99 + 8n < 100

n > 12.3 and n < 24.8

n = 13, 14, 15,…., 24

So there are 12 values of n and hence 12 potential values of x.

We go with option (E). Cool, isn’t it? 🙂

Liked this? Find Data sufficiency challenging? Check out the most comprehensive advanced Data sufficiency practice guide