Divisibility

[Deepthi Subbu]

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.

[Anurag@Gurome]

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 .

[MAAJ]

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...

[Adam@Knewton]

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.

[[email protected]]

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)))

[Adam@Knewton]

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!

[Anurag@Gurome]

@Maaj: I missed a point to mention. Edited the reply accordingly. Check it.

[MAAJ]

Thank you all for the comments, my curiosity has been satisfied