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 (x _{i}, y_{i}) are possible such that 7x_{i} – 8y_{i} = 99 and 0 < x_{i} < 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 (x _{n}, y_{n}) are represented by :**

**x _{n} = x_{1} – nb/gcd(a,b)**

**y _{n} = y_{1} + na/gcd(a,b)**

**where n is any integer and x _{1} and y_{1 } are any random integer solutions of the equation such that ax_{1} + by_{1} = 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 :

x_{n} = x_{1} – nb/GCD(a,b)

y_{n} = y_{1} + na/GCD(a,b)

..so we need x_{1} and y_{1 } (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 x_{1} and y_{1 } (the random solutions) such that :

3x_{1} + 14y_{1} = 20

One way is to just guess (x_{1}, y_{1}). 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(x_{k}) + 14(y_{k}) = 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, x_{k } = 5 and y_{k} = -1

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

3(x_{k}) + 14(y_{k}) = 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, x_{1} = 100 and y_{1} = -20

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

x_{n} = x_{1} – nb/GCD(a,b)

y_{n} = y_{1} + na/GCD(a,b)

x_{n} = 100 – 14n

y_{n} = -20 + 3n

**Go ahead! Try any integer value of n and you will have x _{n} and y_{n} 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

x_{n} = x_{1} – nb/GCD(a,b)

y_{n} = y_{1} + na/GCD(a,b)

x_{n} = -99 – n (-8) = – 99 + 8n

y_{n} = 99 + n(7) = 7n + 99

Now, 0 < x_{n }< 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