BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Question on modulo arithmetic

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Senior | Next Rank: 100 Posts
Posts: 85
Joined: Sat Jan 01, 2011 11:57 am
Thanked: 1 times

Question on modulo arithmetic

by OneTwoThreeFour » Sat Apr 23, 2011 10:38 am
If t is a positive integer and r is the remainder when t^2 + 5t+6 is divided by 7, what is the value of r?

(1) When t is divided by 7, the remainder is 6.
(2) When t^2 is divided by 7, the remainder is 1.

My question is primarily on statement one. According to modulo arithmetic, the remainder for statement 1 is 2, since
remainder of t^2 is 36/7=1, 5t is 30/7=2, and remainder of 6/7 is 6. Thus 1+2+6=9 and 9-7=2. So the value of r is 2.

The proof for remainder of 5t/7 is given by:

t/y=Q + r/y (Where y is the divisor, r is the remainder, and Q is the quotient.)
5 * (t/y) = 5Q + 5r/y
This works, but my proof for t^2/7 is:
t * (t/y)= tQ + t*r/y. (t*r/y cannot equal to t^2/y for all circumstances.)
So what I am doing wrong? I know that the remainder for t^2/y is the same as r^2/y, so what is a correct proof for t^2/y?

Secondly, is there a quicker way to solve statement 2 from a conceptual approach instead of picking numbers?

Thanks!
Top
Source: — Data Sufficiency |

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2623
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Sat Apr 23, 2011 4:31 pm
A few things here:

- just as you wouldn't try to prove the Pythagorean Theorem is true in the middle of a test, nor should you be trying to prove modular arithmetic works in the middle of a test. If you know it, and find a question where you can use it, then use it, but don't try to prove it unless you have a lot of free time;

- test takers are not expected to know modular arithmetic, and on any question where you might be able to use it, there will be alternative approaches available. That said, modular arithmetic can occasionally save time, but only on some very high level questions. Unless you are scoring in the 45-51 range in Quant, you simply won't see any questions where you could even consider using modular arithmetic - that's the nature of an adaptive test - and it would be pointless to study it;

- modular arithmetic basically says: if you're dividing everything by a fixed number (like in the above question, we're dividing everything only by 7) and you need to find the remainder when you divide some sum, difference, or product by that number, then you don't need to care about quotients at all - you can just work with the remainders. So to give some examples:

If the remainder is 5 when x is divided by 7, and the remainder is 6 when y is divided by 7, what is the remainder when xy is divided by 7?

We can just use the remainders: xy = 5*6 = 30. So the remainder when xy is divided by 7 is 2.

If the remainder is 2 when x is divided by 11, what is the remainder when x^2 + 5x is divided by 11?

Again, we can just use the remainder: (2)^2 + 5(2) = 14, so the remainder is 3 when x^2 + 5x is divided by 11.

If you apply that to the question above, you can see instantly that Statement 1 is sufficient.

Now if you actually wanted to *prove* that this works - that is, that the quotient is irrelevant here - that takes some time, time better spent doing other things if you're in the middle of a test. But we can do it: say the remainder is 6 when t is divided by 7. We can prove the remainder will always be 1 when t^2 is divided by 7. We know

t = 7q + 6

where q is the integer quotient. So

t^2 = (7q + 6)^2 = (7^2)(q^2) + (2)(6)(7q) + 36 = (7^2)(q^2) + (2)(6)(7q) + 35 + 1

Notice that every term is a multiple of 7 besides the '1' at the end, so t^2 is 1 more than a multiple of 7, which is another way of saying that the remainder is 1 when t^2 is divided by 7.

Similarly, if we want the remainder when 5t is divided by 7:

5t = 5(7q + 6) = 35q + 30 = 35q + 28 + 2

so 5t is 2 more than a multiple of 7, which means the remainder is 2 when 5t is divided by 7.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com
Top
Senior | Next Rank: 100 Posts
Posts: 85
Joined: Sat Jan 01, 2011 11:57 am
Thanked: 1 times

by OneTwoThreeFour » Sun Apr 24, 2011 8:53 am
Thanks Ian! Haha, I will certainly not be trying to do proofs on the actual gmat. The proof you gave me contains numerical values for the divisor and remainder. That I understand. Is there no proof where t^2/y= R^2/y when t=yQ +R? (Where we are not given any numerical values at all) It's not important since the proof you gave w/ numerical values for divisor and remainder is sufficient for my understanding of modulo arithmetic.

As for statement 2, is there a simpler way to approach it from a conceptual approach?
I could pick t=6, and 1, for t^2/7 and get remainders of 1, but get two different remainders when it is (t^2 + 5t +6) /7. But, I want to avoid picking numbers as much as possible on the real gmat, so is there some mathematical rule that dictates statement 2 is false?

The reason I want to learn additional math such as modulo arithmetic is b/c I am scoring 48s in the Quant right now, and I need all the edge I can get to get myself a 50/51.

Once again, thank you so much for your help!
Top

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2623
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Sun Apr 24, 2011 11:01 am
OneTwoThreeFour wrote:Thanks Ian! Haha, I will certainly not be trying to do proofs on the actual gmat. The proof you gave me contains numerical values for the divisor and remainder. That I understand. Is there no proof where t^2/y= R^2/y when t=yQ +R? (Where we are not given any numerical values at all) It's not important since the proof you gave w/ numerical values for divisor and remainder is sufficient for my understanding of modulo arithmetic.
The proof is exactly the same, just with letters instead of numbers - this is all going to be pretty abstract, and it's not essential for the test, so most people can just skip this post, but out of interest: If we know the remainder is r when n is divided by d, then we know that n = qd + r, where q is the quotient. Say we want to know the remainder when n^2 is divided by d. Then

n^2 = (qd + r)^2 = (q^2)(d^2) + 2qdr + r^2

Notice that everything here is a multiple of d besides r^2, so n^2 is just r^2 greater than some multiple of d; the terms besides the r^2 are irrelevant if we only care about the remainder. So r^2 *is* the remainder if r^2 is small enough (if r^2 < d), and if not, we would just need to take the remainder when r^2 is divided by d to get the answer.


OneTwoThreeFour wrote: As for statement 2, is there a simpler way to approach it from a conceptual approach?
I could pick t=6, and 1, for t^2/7 and get remainders of 1, but get two different remainders when it is (t^2 + 5t +6) /7. But, I want to avoid picking numbers as much as possible on the real gmat, so is there some mathematical rule that dictates statement 2 is false?
At some point, when considering Statement 2, you need to notice that t can have two different remainders (1 and 6) when divided by 7; I don't see any way to avoid that. I suppose when I look at Statement 2, I notice two things:

* if the remainder is 1 when t^2 is divided by 7, then t^2 + 6 is a multiple of 7. So I can rephrase the question: 'what is the remainder when 5t is divided by 7?' By modular arithmetic, that's the same question as 'what is the remainder when t is divided by 7?'

* if you think of the equation t^2 = 1, there are two solutions: 1 and -1. A similar thing will happen here; it's just a modular arithmetic equation now. The remainder can be 1 when t is divided by 7, or it can be 'equivalent to' -1. Since we preserve remainders if we add 7, a remainder of 6 is 'equivalent to' -1, so 1 and 6 are our two possible remainders for t. It's also quite fast just to test the different possible remainders from 1 through 6 - nothing wrong with that approach.


Finally, about your reluctance to pick numbers: if you need to prove that a statement is *not* sufficient in DS, sometimes you have to pick numbers; you need to generate two scenarios that give you different answers to the question. It can sometimes be difficult or impossible to prove that a statement is *not* sufficient by using pure algebra or conceptual reasoning. So if you suspect that one statement (or both together) is not sufficient, and you want to be sure of your answer, don't reject number-picking as a strategy; if you can come up with two scenarios that give two different answers to the question, you can be 100% certain the information is not sufficient. It's when you are trying to prove that information *is* sufficient that you often want to be wary of number-picking, since you won't necessarily be completely sure of your answer, but even in that case it's a good fallback strategy if you don't see how to 'prove' a statement is sufficient.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com
Top
Senior | Next Rank: 100 Posts
Posts: 85
Joined: Sat Jan 01, 2011 11:57 am
Thanked: 1 times

by OneTwoThreeFour » Sun Apr 24, 2011 3:54 pm
Thanks Ian! That was an awesome reply and some very shrewd advice.
Top
Post new topic Post Reply
• Page 1 of 1