The Common Admissions Test (CAT) is unique in that it tests some areas of mathematics that other tests do not, such as remainders, modular arithmetic, and different number bases. In this article, you’ll learn what you need to know about CAT remainder problems. Then you’ll get your chance to practice on problems similar to those on an actual CAT.

For more about mathematics topics on the CAT, check out the Math Syllabus for CAT Exam.

## Long Division and Finding Remainders

It all begins with division.

In elementary and middle school, you learned a process called **long division**.

One easy and useful thing to remember is that the remainder must always be *less than* the divisor. For example, if you divide any number *N* by the divisor 2, then your remainder can only be 0 (if *N* is *even*) or 1 (if *N* is *odd*).

In fact, a number *N* is **divisible** by *d* if and only if the remainder of the division *N* ÷ *d* is equal to 0.

If you take the remainders of consecutive whole numbers with respect to a fixed divisor *d*, then you end up with consecutive remainders… most of the time. The only exception is that the next remainder after *d*-1 must be 0.

*Confused?* Let’s look at an example.

The first row of the table shows consecutive whole numbers from 1 to 10. The second row shows their remainders upon division by *d* = 4. See how the remainders also increase by 1 until you hit *d* – 1 = 3?

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 |

## Remainder Properties and Formulas

Long division can be a pain in the neck. Fortunately, there are ways to avoid this step sometimes when finding remainders.

Remainders work pretty well with respect to addition, subtraction, and multiplication. Just as long as you’re working with the same divisor throughout.

- If you add two numbers and then take the remainder, it’s the same as if you first took remainders and then added.
- The same is true for subtraction. If you subtract two numbers and then take the remainder, it’s the same as if you first took remainders and then subtracted.
- And it works for multiplication too! If you multiply two numbers and then take the remainder, it’s the same as if you first took remainders and then multiplied.

The only caveat is that you still might have to take remainders again at the end of each operation. We call this process **modular arithmetic**. Then we call the divisor the **modulus**, and finding remainders by a modulus *d* will often be called **reduction (modulo d)**.

For example, what is the remainder when 250 is divided by 7? Instead of long division, just think of 250 as 25 × 10. The remainder for 25 ÷ 7 is 4 (since 25 = 7(3) + 4), and for 10, the remainder is 3. Multiply remainders to get 4 × 3 = 12. Then reduce again by 7 to find the remainder 5 to answer the problem.

By the way, because modular arithmetic works with multiplication, that means you can take whole number powers as well!

For example, what is the remainder of 2^{301} ÷ 3? First, note that 2^{2} = 4 reduces to 1 modulo 3. Rewrite 2^{301} = 2^{2(150) + 1} = 4^{150}× 2. Then by the rules for modular arithmetic, the remainder will be the same as for 1^{150} × 2, which is equal to 2.

## Euler’s Theorem — Advanced Topic

Finding remainders of large powers divided by large divisors can be very time-consuming. Fortunately, there is a mathematical “trick” that can speed the process along.

**Euler’s Theorem.** If *m* and *n* are relatively prime (no common factors except 1), then there is a special number called φ(*n*) such that the remainder of the division *m*^{φ(n)} ÷ *n* is always 1. The value of φ(*n*) is given by the formula,

An example showing the use of this advanced formula will be given in the practice problems.

## CAT Remainder Practice Problems

Now you can try your hand at each of these CAT remainder practice problems! Solutions appear at the end.

### Problem 1

Find the sum of all two-digit numbers that leave a remainder of 3 when divided by 7.

(A) 503 (B) 676 (C) 777 (D) 832

### Problem 2

What is the remainder of 3^{2017} upon division by 82?

(A) 3 (B) 15 (C) 27 (D) 51

### Problem 3

What is the remainder of 3^{2053} upon division by 83?

(A) 3 (B) 16 (C) 27 (D) 51

### Problem 4

Suppose *x* = *k*(*k*+1)(*k*+2), where *k* ε **N**. What must be true about the number *x*?

(A) *x* is even and divisible by 7.

(B) *x* is not divisible by 5.

(C) *x* is odd and divisible by 3.

(D) *x* is divisible by 6.

### Problem 5

A two-digit number *n* has remainders 1, 1, and 6 when divided by 3, 5, and 7, respectively. Find the sum of digits of *n*.

(A) 9 (B) 11 (C) 13 (D) 14

## Solutions

Are you ready to check your work?

### Solution to Problem 1

(B) 676

Because remainders of consecutive whole numbers form a repeating consecutive list, we know that all numbers having a certain remainder will form an **arithmetic sequence**. This sequence starts as follows (remember, we just want two-digit numbers):

10, 17, 24, 31, …

To find out the last number in the sequence, find the remainder of 99 ÷ 7, which is 1. So, working backward, the last number in the sequence whose remainder will be 3 must be 94.

Then you can use the formula for a sum of an arithmetic sequence. How many terms will be there? well if *a*_{1} = 10 = 7(1) + 3, and *a _{n}* = 7(

*n*) + 3 = 94, then solve to get

*n*= 13.

Sum = (*n*/2)(*a*_{1} + *a _{n}*) = (13/2)(10 + 94) = 676.

### Solution to Problem 2

(A) 3

Remainders and modular arithmetic show up in two different ways in this problem.

First, let’s explore some of the small powers of 3. 3^{1} = 3, 3^{2} = 9, 3^{3} = 27, 3^{4} = 81. The fact that 81 is only 1 less than the modulus 83 is a big clue. This means that 81 is equivalent to -1 modulo 82.

Now let’s find out how many groups of 4 are in 2017. Using long-division, we find that 2017 = 4(504) + 1. So we can rewrite the original value:

3^{2017} = (3^{4})^{504} × 3^{1},

which is equivalent to: (-1)^{504} × 3 = 1 × 3.

Therefore the remainder is 3.

### Solution to Problem 3

(C) 27

If you think you’ve seen double, take a closer look! This time the divisor is 83. If you tried the same procedure as the previous problem, then you immediately hit a snag. 3^{4} is equivalent to -2 modulo 83, and it’s a lot harder to deal with powers of -2 then with powers of -1.

This is a job for Euler’s Theorem. Because *n* = 83 is prime, it only has a single prime factor, and we get:

φ(83) = 83(1 – 1/83) = 83 – 1 = 82.

The theorem states that 3^{82} will have remainder 1 when divided by 83. So now let’s reduce the exponent 2053 modulo 82 by long division. The remainder happens to be 3.

So, 3^{2053} is equivalent to 3^{3} = 27.

### Solution to Problem 4

(D) *x* is divisible by 6.

A little knowledge of remainders helps out. Notice that *x* is the product of three *consecutive* natural numbers: *k*, *k*+1, and *k*+2. (Recall, **N** is the set of natural numbers, 1, 2, 3, 4, ….)

So if you took remainders of the three factors with respect to the divisor 2, you’d get either 0, 1, 0, or 1, 0, 1. Then when you multiply them, you’d get 0 as a remainder of *x* by 2.

Thus, *x* is even. But that’s not all!

Taking remainders of *k*, *k*+1, and *k*+2 by the divisor 3 would result in a list like 0, 1, 2, or 1, 2, 0, or 2, 0, 1. No matter what, 0 will show up in the list. So when we multiply those remainders together we end up with 0.

Thus, *x* is divisible by 3.

Any number divisible by both 2 and 3 must be divisible by 6.

### Solution to Problem 5

(C) 13

Let’s work backward.

Because *n* has remainder 1 when divided by 3, we know that *n* = 3*a* + 1 for some *a* ε **N**.

Next, we reason that 3*a* must be divisible by 5 (so that *n* = 3*a* + 1 has the required remainder of 1 upon division by 5). Therefore, since 3 is relatively prime to 5, we know that 5 has to be to be a factor of *a*. We can now replace *a* by 5*b* (for some *b* ε **N**). That is,

*n* = 3(5*b*) + 1 = 15*b* + 1.

Finally, reduce the number modulo 7. Noting that 15 = 2(7) + 1, we find that *n* is equivalent to *b* + 1 mod 7. Then *b* = 5 is the smallest possibility that would give the required remainder of 6 mod 7.

To find *n*, simply plug in *b* = 5 to get *n* = 15(5) + 1 = 76. Finally, the sum of digits is 7 + 6 = 13 to answer the problem.

## Final Thoughts

Now that you’ve studied a few practice problems and their solutions, you should be a little better prepared for the test.

Although CAT remainder problems can be challenging, it’s important to remember the basics.

- Know how to use long division to find quotients and remainders.
- Understand the patterns in how remainders appear for consecutive whole numbers.
- Use the additive, subtractive, and multiplicative properties of remainders (modular arithmetic).
- Look for those mathematical methods and theorems (such as Euler’s Theorem) that will allow you to work out remainders of a large power of a number.

With these tips in mind, you’ll be sure to succeed on the CAT!

By the way, sign up for our 1 Week Free Trial to try out Magoosh GMAT Prep!

## No comments yet.