Divisibility

This topic has expert replies
Master | Next Rank: 500 Posts
Posts: 298
Joined: Tue Feb 16, 2010 1:09 am
Thanked: 2 times
Followed by:1 members

Divisibility

by Deepthi Subbu » Mon Jan 10, 2011 10:13 pm
If p and n are positive integers and p > n, what is the remainder when p2 - n2 is divided by 15 ?

(1) The remainder when p + n is divided by 5 is 1.

(2) The remainder when p - n is divided by 3 is 1.

For prob under this category (divisibility) is there a shortcut to choose numbers as it is highly time consuming to try out different combination of numbers.
Source: — Data Sufficiency |

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 3835
Joined: Fri Apr 02, 2010 10:00 pm
Location: Milpitas, CA
Thanked: 1854 times
Followed by:523 members
GMAT Score:770

by Anurag@Gurome » Mon Jan 10, 2011 10:40 pm
Deepthi Subbu wrote:If p and n are positive integers and p > n, what is the remainder when p² - n² is divided by 15 ?

(1) The remainder when p + n is divided by 5 is 1.
(2) The remainder when p - n is divided by 3 is 1.
Yes you can select numbers carefully which will save an enormous amount time in this problem. But to do so you must have a good idea about numbers. Choose the numbers such that they satisfy both statement.

Note that for integer values of p and n, the values of (p + n) and (p - n) must be either both even or both odd. If one of them is even and other one is odd, we will get fractional values for p and n. Let's proceed with both odd case.

Statement 1 says, the remainder when p + n is divided by 5 is 1.
As we are considering odd values of (p + n), (p + n) can be 11, 21, 31 etc

Statement 2 says, the remainder when (p - n) is divided by 3 is 1.
As we are considering odd values of (p - n), (p - n) can be 1, 7, 13, 17 etc

Now, note that for each possible value of (p + n), we can always choose (p - n) to be equal to 1. For example, (p + n) = (6 + 5) = 11 => (p - n) = (6 - 5) = 1. Same goes for other values.

This helps us to conclude that for each possible values of (p + n), the value of (p² - n²) = (p - n)(p + n) can be equal to the value of (p + n) itself. As (p - n) always can be equal to 1.

Now some of the possible values of (p² - n²) are 1, 21, 31 etc.
Each of them gives different remainder when divided by 15.

Hence we can conclude that both the statement together is also not sufficient to answer the question as our numbers satisfies all the conditions provided.

The correct answer is .
Last edited by Anurag@Gurome on Tue Jan 11, 2011 8:33 pm, edited 1 time in total.
Anurag Mairal, Ph.D., MBA
GMAT Expert, Admissions and Career Guidance
Gurome, Inc.
1-800-566-4043 (USA)

Join Our Facebook Groups
GMAT with Gurome
https://www.facebook.com/groups/272466352793633/
Admissions with Gurome
https://www.facebook.com/groups/461459690536574/
Career Advising with Gurome
https://www.facebook.com/groups/360435787349781/

User avatar
Master | Next Rank: 500 Posts
Posts: 243
Joined: Sun Jul 12, 2009 7:12 am
Location: Dominican Republic
Thanked: 31 times
Followed by:2 members
GMAT Score:480

by MAAJ » Tue Jan 11, 2011 2:59 pm
Statement 1 says, the remainder when p + n is divided by 5 is 1.
Thus (p + n) must be odd, hence (p - n) can be 11, 21, 31 etc

Statement 2 says, the remainder when (p - n) is divided by 3 is 1.
Thus (p - n) must be odd, hence we choose (p - n) can be 1, 7, 13, 17 etc
Can we conclude that (p + n) is odd knowing that: "if (p + n) is divided by 5, the remainder is 1"?
  • I tried different values for (p + n) = 5q + 1 (q for quotient) and I concluded that (p + n) could be: 1, 6, 11, 16, 21, 26, ... note that there are even and odd numbers in the list, am I missing something?
Can we conclude that (p - n) is odd knowing that: "if (p - n) is divided by 3, the remainder is 1"?
  • Also tried different values for (p - n) = 3q + 1 and concluded that (p - n) could be: 1, 4, 7, 10, 13, 16, ... Same as above, getting even and odd numbers...
"There's a difference between interest and commitment. When you're interested in doing something, you do it only when circumstance permit. When you're committed to something, you accept no excuses, only results."

User avatar
GMAT Instructor
Posts: 132
Joined: Mon Jan 10, 2011 12:26 pm
Location: New York City
Thanked: 68 times
Followed by:37 members
GMAT Score:780

by Adam@Knewton » Tue Jan 11, 2011 3:23 pm
Remember, to prove something Insufficient, you only need a couple of examples of numbers, so in actuality it doesn't become too time-consuming. If you realize quickly that the question is really asking about (p+n)(p-n), then you'll see quickly that each Statement is Insufficient on its own, but maybe, just maybe, they're Sufficient together.

You're totally right about Statement (1): it could mean that p+n = 6 or 11 or some other numbers. Similarly, Statement (2) gives us p-n = 4 or 7 or some other numbers. Given, this, (p+n)(p-n) could be, say, 24 (remainder of 9 when divided by 15) or 77 (remainder of 2 when divided by 15). Very quickly, we get 2 different answers, and it's Insufficient.

What if, somehow, we'd received the same answer both times? It would be a heck of a coincidence for that to happen! On weird Number Properties questions like Remainders questions, we shouldn't believe much in coincidence. If somehow using 6 & 4 gave us the same answer as using 11 & 7, then you should feel pretty confident saying it's Sufficient Together and picking C.

Finally, in case you really feel like doing some theory, let's treat it algebraically:
Statement (1) --> (p+n)=5m+1 (m is an integer)
Statement (2) --> (p-n)=3n+1 (n is an integer)

(p+n)(p-n) = (5m+1)(3n+1) = 15mn + 5m + 3n + 1. Now, what's the remainder when this is divided by 15?

Well, it depends on m and n, after all. If m=n=3, then you'll have a remainder of 10 (just the 3n+1 part; the rest is clearly divisible by 15). If you have m=n=2, then only the 15mn part is divisible by 15, so add to that 5m+3n+1=17 and your remainder will be 2.

I don't like that way of doing it, BUT, sometimes that's the way to see Sufficiency more clearly than plugging in numbers. For example, if somehow your algebra gave you something like 15mn + 15m + 3 (on some other crazy problem, that is), then you'd know for certain the remainder is 3, and not have to second-guess yourself.

Remember: When plugging in numbers, just 2 different answers is enough to say Insufficient, and oftentimes 2 same answers can make you 90% sure enough to say Sufficient. However, the only way to prove Sufficiency is with number theory, just as the best way to prove Insufficiency is usually with plugging in numbers.
Prep Smarter, Score Higher
www.knewton.com

Newbie | Next Rank: 10 Posts
Posts: 3
Joined: Wed Nov 24, 2010 10:08 am

by [email protected] » Tue Jan 11, 2011 3:37 pm
Well, as it looks to me: both statements are insufficient.

I think it is pretty much clear that each statement by itself is not sufficient since there are several combinations of the numbers which meet requirenment (p+n)/5 with remainder 1. Even if we consider the the smallest possible value which is 6, we can come up with different combinations for (p-n) to meet the requirenment p>n (5 and 1; 4 and 2). Hence remainders will be different.
Second statement gives us different numbers as well since we simply have to meet the requirenment (p-n)= 3q+1

To consider to statements together I picked 2 smallest possible numbers, and answers were different:

(p+n)=6 =>>> P= 5; N=1 =>> ((5-1)*(5+1))/15=24/15 =>> remainder 9
(p+n)=16 =>>> P=10; N=6 =>> ((10-6)*(10+6))/15=64/15 =>> remainder 4

I am not really good at DS. Please correct me if I am missing something)))

User avatar
GMAT Instructor
Posts: 132
Joined: Mon Jan 10, 2011 12:26 pm
Location: New York City
Thanked: 68 times
Followed by:37 members
GMAT Score:780

by Adam@Knewton » Tue Jan 11, 2011 3:45 pm
Svetlana: Excellent job, you're not missing anything! I will point out that, myself, I didn't think of p and n separately, but rather just plugged in values for (p+n) and (p-n). However, I actually think my initial approach, while a little speedier, was a little sloppy in comparison with yours, because we're told that p and n are positive integers, so theoretically not every combination of p+n and p-n will actually be allowed on this problem. Nice job sticking to the requirements of the problem and proving Insufficiency with some clear, easily-plugged-in numbers! :)
Prep Smarter, Score Higher
www.knewton.com

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 3835
Joined: Fri Apr 02, 2010 10:00 pm
Location: Milpitas, CA
Thanked: 1854 times
Followed by:523 members
GMAT Score:770

by Anurag@Gurome » Tue Jan 11, 2011 8:34 pm
@Maaj: I missed a point to mention. Edited the reply accordingly. Check it.
Anurag Mairal, Ph.D., MBA
GMAT Expert, Admissions and Career Guidance
Gurome, Inc.
1-800-566-4043 (USA)

Join Our Facebook Groups
GMAT with Gurome
https://www.facebook.com/groups/272466352793633/
Admissions with Gurome
https://www.facebook.com/groups/461459690536574/
Career Advising with Gurome
https://www.facebook.com/groups/360435787349781/

User avatar
Master | Next Rank: 500 Posts
Posts: 243
Joined: Sun Jul 12, 2009 7:12 am
Location: Dominican Republic
Thanked: 31 times
Followed by:2 members
GMAT Score:480

by MAAJ » Wed Jan 12, 2011 5:15 am
Thank you all for the comments, my curiosity has been satisfied :)
"There's a difference between interest and commitment. When you're interested in doing something, you do it only when circumstance permit. When you're committed to something, you accept no excuses, only results."