Last visit was: 20 Jul 2024, 06:45 It is currently 20 Jul 2024, 06:45
Close
GMAT Club Daily Prep
Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History
Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.
Close
Request Expert Reply
Confirm Cancel
SORT BY:
Date
Tags:
Show Tags
Hide Tags
Math Expert
Joined: 02 Sep 2009
Posts: 94428
Own Kudos [?]: 642490 [80]
Given Kudos: 86669
Send PM
Most Helpful Reply
GMAT Club Legend
GMAT Club Legend
Joined: 03 Oct 2013
Affiliations: CrackVerbal
Posts: 4918
Own Kudos [?]: 7807 [36]
Given Kudos: 221
Location: India
Send PM
General Discussion
Current Student
Joined: 06 Jul 2021
Posts: 10
Own Kudos [?]: 2 [0]
Given Kudos: 9
Location: New Zealand
GMAT 1: 710 Q49 V38
GPA: 3.7
Send PM
GMAT Tutor
Joined: 24 Jun 2008
Posts: 4128
Own Kudos [?]: 9455 [0]
Given Kudos: 91
 Q51  V47
Send PM
Re: Remainders: Tips and hints [#permalink]
Expert Reply
CrackVerbalGMAT wrote:
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.



That is not the "Euclidean division algorithm". Euclid's division algorithm is an algorithm (a set of step by step instructions) that can be used to find the GCD of two numbers, but it's not something anyone should ever use on the GMAT (there are better ways to find GCDs on the GMAT).

The equation y = xq + r, with the inequality on r, is just an algebraic way of defining quotients and remainders. "Euclid's division lemma" (which is what I imagine was meant here instead of 'algorithm') states this definition, but the point of Euclid's lemma is that the values q and r are unique. It's not a particularly advanced mathematical fact, but whenever we divide one positive integer by another, there can only ever be one correct quotient and one correct remainder -- that's the substance of Euclid's division lemma.
Intern
Intern
Joined: 22 Jun 2020
Posts: 33
Own Kudos [?]: 16 [0]
Given Kudos: 51
Location: India
GMAT 1: 700 Q50 V34
GPA: 3.36
Send PM
Re: Remainders: Tips and hints [#permalink]
macvaluemeal wrote:
Thanks for the explanation! One thing I dont understand is why the remainder cycle ends once the remainder is 1 - can you please elaborate?

bb Bunuel I don't get this as well. Can you help please?
Math Expert
Joined: 02 Sep 2009
Posts: 94428
Own Kudos [?]: 642490 [1]
Given Kudos: 86669
Send PM
Re: Remainders: Tips and hints [#permalink]
1
Bookmarks
Expert Reply
wolfman wrote:
macvaluemeal wrote:
Thanks for the explanation! One thing I dont understand is why the remainder cycle ends once the remainder is 1 - can you please elaborate?

bb Bunuel I don't get this as well. Can you help please?


The example you are referring to considers the remainder of 7^27 divided by 9

7^1 = 7 divided by 9 gives the remainder of 7;
7^2 = 49 divided by 9 gives the remainder of 4;
7^3 = 343 divided by 9 gives the remainder of 1;
7^4 = 2401 divided by 9 gives the remainder of 7;
...

As you can see the remainders after 7^3 start to repeat: 7, 4, 1, 7, 4, 1, 7, 4, 1, ... So, the cycle is {7, 4, 1}. Thus, the remainder of 7^27 divided by 9 will be 1 (the power, 27, is a multiple of 3, so 7^3, 7^6, 7^9, ..., 7^27, will all have the same remainder).

For more on this kind of questions check Units digits, exponents, remainders problems collection.
Manager
Manager
Joined: 30 Dec 2021
Posts: 51
Own Kudos [?]: 9 [0]
Given Kudos: 71
Send PM
Re: Remainders: Tips and hints [#permalink]
CrackverbalGMAT wrote:
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 with 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


Hey,
Thanks for this article but can you please explain in the 2nd way how did 234k came isn't just 169k^2 + 81 should be there? What am I missing here?
User avatar
Non-Human User
Joined: 09 Sep 2013
Posts: 34038
Own Kudos [?]: 853 [0]
Given Kudos: 0
Send PM
Re: Remainders: Tips and hints [#permalink]
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
GMAT Club Bot
Re: Remainders: Tips and hints [#permalink]
Moderator:
Math Expert
94428 posts