Remainders: Tips and hints

Questions on remainders are quite frequent on the Quant section of the GMAT. This is probably because of the fact that a question on remainders tests your logical reasoning abilities along with the mathematical concepts involved.

If x and y are positive integers, there exist unique integers q and r, called the quotient and remainder, respectively, such that y = xq + r and 0 ≤ r < x .

As Bunuel has already highlighted in his introductory post, the mathematical statement shown above forms the crux of the discussion on Remainders. It’s known as the Euclidean division algorithm.


Note that the algorithm mentions that all the quantities involved in the equation are positive integers. So, can we not have negative remainders? Not on the GMAT. On the GMAT, remainders are always taken to be positive.

So, what are remainders? I’m just surmising here; but the concept of remainders may have evolved from the fact that, when we were hunter-gatherers, there may have been situations when a person had to distribute (i.e. to divide) the spoils (food/tools etc.,) among his/her companions evenly. Whatever was left over was the remainder.

As I said, I’m just surmising that it may have started off like this. But I hope this has given you a simpler way of understanding remainders.

Now, let us look at different methods of calculating remainders. Obviously, we cannot have a ‘One size fit all’ approach in all remainder questions, so let’s look at different methods to suit different question types.

1) Using Divisibility Rules
2) Remainder Theorem
3) Use the Euclidean Algorithm
4) Use the Remainder cycle

1) Using Divisibility Rules to determine the remainder:

This is by far the simplest way of finding remainders without actually dividing the number. Naturally, you are expected to know the divisibility rules of commonly tested numbers. For example, if we have to find the remainder when 11257983 is divided by 8 without dividing, how do we do it?

Well, we apply the divisibility rule for 8 on the given number. The divisibility rule for 8 is,
‘If the last 3 digits of the given number forms a number divisible by 8 or if the last 3 digits of the given number are zeroes, then the number is divisible by 8.’

In our number, the last three digits forms 983. When we divide 983 by 8, we get a remainder of 7. You will see that if 11257983 is divided by 8, the remainder will be 7 as well.

The limitation of this approach is that it cannot be applied in cases where the dividend and the divisor are not clearly defined.


2) Using the remainder theorem:

When I mention remainder theorem, I’m not referring to the polynomial remainder theorem that all of us learnt in Algebra in high school.

The remainder theorem says that if you have a fairly large number to be divided so as to get a remainder, you can break up the large number as a sum/product of smaller numbers, obtain remainders by dividing the smaller parts with the original divisor and then finally add/multiply the respective remainders to get the final remainder.

Well, that’s a lot to understand in one go. Do not worry, let’s take some simple examples to understand how this theorem can be applied to solve Remainder questions.

Let’s say we have to find the remainder when 2310 is divided by 17. Obviously, one way is to divide the number directly, but in our case, let’s not do that since we are trying to learn a new method.
You see that 2310 can be broken up as 2310 = 1700 + 510 + 100. When we divide the individual parts by 17, we get 0,0 and 15 as the respective remainders.

Why did I break 2310 specifically as 1700, 510 and 100? Think about it!

The final remainder is obtained by adding these remainders and dividing by the original divisor. Adding the remainders, we get the sum as 15. When 15 is divided by 17, the remainder is 15 itself, since the dividend is smaller than the divisor (this concept has already been explained by Bunuel in his post).

Another way of expressing 2310 is 2310 = 30 * 77. When we divide the individual parts by 17, we get 13 and 9 as the remainders.

The final remainder is obtained by multiplying these remainders and dividing by the original divisor. Multiplying the remainders, we get the product as 117. When 117 is divided by 17, the remainder is 15.

You see that, regardless of how you break up a larger number into parts, you obtain the same remainder and that is the USP of this approach. This approach reduces the burden of having to deal with a larger number, by letting you break it into smaller parts that can be divided easily.

3) Use the Euclidean Algorithm itself:

A lot of remainder questions on the GMAT test your ability to develop an equation using the Euclidean algorithm and solve the equation to get the remainder.

To reiterate,

If x and y are positive integers, there exist unique integers q and r, called the quotient and remainder, respectively, such that y = xq + r and 0 ≤ r < x .

Now, how do we use this algorithm to develop equations and find remainders? Let’s take an example.

The remainder when N is divided by 13 is 9. What is the remainder when the square of N is divided by the same divisor?

In this question, the divisor is 13, the dividend is N and the remainder is 9. If the quotient in this division is k, using the algorithm we can say,

N = 13*k + 9.

Now that we know what N is, finding out N^2 is easy. \(N^2\) = \((13k + 9)^2\), which simplifies to \(N^2\) = 169\(k^2\) + 234k + 81 when we apply the \((a+b)^2\) identity.

We are to divide \(N^2\) by 13. Now, as you observe, \(N^2\) is a fairly large number, but the good thing is we have already broken it up into three parts (remember what we did with 2310 in the previous approach). Now, all that is left is to find out the respective remainders and then add them up to obtain the final remainder.

If we divide 169\(k^2\) by 13, the remainder will be 0 since 169 is divisible by 13. The remainder when 234k is divided by 13 is also 0 since 234 is also divisible by 13. The only remainder will come from the third part i.e. 81; when 81 is divided by 13, the remainder is 3.

So, the final remainder = 0 + 0 + 3 = 3.

An alternative approach here is to plug in values for the quotient k.
If k = 0, N = 9 and \(N^2\) = 81. When 81 is divided by 13, the remainder is 3.
If k = 1, N = 22 and \(N^2\) = 484. When 484 is divided by 13, the remainder is 3.

This should be sufficient for us to conclude that the remainder will always be 3.

As you see, the remainder theorem finds its uses here as well when we try to solve the question using the algorithm. The limitation of using the Euclidean algorithm in forming equations is that it can throw up quadratic or cubic equations which are time consuming to solve.

4) Using the Remainder Cycle:

This is a method that I personally like using, especially when my dividend has exponents. Bear in mind that, when applying this approach, try to express the dividend or some part of the dividend as (divisor + 1).

Let us take an example to understand. When \(7^{27}\) is divided by 9, what is the remainder?

When \(7^1\) is divided by 9, the remainder is 7.
When \(7^2\), 49, is divided by 9, the remainder is 4.
When \(7^3\), 343, is divided by 9, the remainder is 1.

In the remainder cycle, the remainder becoming 1 means the end of the cycle. So, in our example, we have a cycle of cyclicity 3.

We are trying to find the remainder when \(7^{27}\) is divided by 9; observe that the power of 7 here is a multiple of 3. Whenever the power is a multiple of 3, we can say that the remainder will be 1 (since the cyclicity of the cycle is 3). Therefore, our required remainder is 1.

If the cycle is longer, my advice to you would be to use the remainder concept to simplify calculations. Let’s take another example to understand how this can be done.

What is the remainder when \(3^{75}\) is divided by 5?

When \(3^1\) is divided by 5, the remainder is 3.
When \(3^2\) is divided by 5, the remainder is 4.
Now, \(3^3\) = \(3^2\) * \(3^1\). So, the remainder when \(3^3\) is divided by 5 will be the product of the respective remainders i.e. 4*3 =12. The remainder is 2 since 12 leaves a remainder of 2 when divided by 5.
Similarly, \(3^4\) = \(3^3\) * \(3^1\). The respective remainders are 2 and 3; product of these = 6. The remainder when 6 is divided by 5 is 1.

Voila! We got 1 in the remainder cycle and now we can say that the cycle will repeat from here with a cyclicity of 4.

Now that we have the cyclicity as 4, we express the dividend in terms of \(3^4\).
\(3^{75} = (3^4)^{18} * 3^3.\)

\({(3^4)^{18}\) is nothing but 3^4 multiplied with itself 18 times; in each case, the remainder is 1.
\(3^3\) divided by 5 gives a remainder of 2.

So, final remainder = 1 * 2 = 2.

The advantage of bringing in the remainder theorem concept of breaking down powers into smaller parts, is that it simplifies things. You don’t have to find the value of \(3^5\) to find the remainder, you can just express it as \(3^3\)* \(3^2\) and take the respective remainders.

The limitation of the remainder cycle method is that the cyclicity is not fixed, it can be different in different cases depending on the dividend and the divisor. As such, it is advisable to use this method only if you are quick with your basic calculations.

I hope this post has provided you some insights into the different methods you can adopt to solve different sorts of remainder questions. However, even when you use any of these approaches, there may be instances where you hit a roadblock and can’t proceed further. Remember that logic, common sense and smart values are your friends in such situations.

Here are a couple of questions related to remainders for all of y’all to practice some of these approaches.

https://gmatclub.com/forum/if-p-is-a-positive-integer-what-is-a-remainder-when-p-2-is-84967.html

https://gmatclub.com/forum/is-x-the-square-of-an-integer-93239.html

https://gmatclub.com/forum/a-b-and-c-are-positive-integers-such-that-when-a-is-divided-by-b-312522.html