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.
