If n is a positive integer and r is the remainder when (n-1)

[rschunti]

If n is a positive integer and r is the remainder when (n-1)(n+1) is divided by 24, what is the value of r?
1). n is not divisible by 2
2). n is not divisible by 3

This is GMATPREP question. What is the best approach to solve these types of questions?

[RonPurewal]

(1)
if n = 3, then (n - 1)(n + 1) = 8, so the remainder is 8
if n = 5, then (n - 1)(n + 1) = 24, so the remainder is 0
insufficient

(2)
if n = 2, then (n - 1)(n + 1) = 3, so the remainder is 3
if n = 5, then (n - 1)(n + 1) = 24, so the remainder is 0
insufficient

(together)
the best approach, unless you're really good at number properties, is to try the first few numbers that satisfy both statements, and watch what happens.
if n = 1, then (n - 1)(n + 1) = 0, so the remainder is 0
if n = 5, then (n - 1)(n + 1) = 24, so the remainder is 0
if n = 7, then (n - 1)(n + 1) = 48, so the remainder is 0
if n = 11, then (n - 1)(n + 1) = 120, so the remainder is 0
...you can see where this is headed.

here's the theory:
- if n is not divisible by 2, then n is odd, so both (n - 1) and (n + 1) are even. moreover, since every other even number is a multiple of 4, one of those two factors is a multiple of 4. so the product (n - 1)(n + 1) contains one multiple of 2 and one multiple of 4, so it contains at least 2 x 2 x 2 = three 2's in its prime factorization.
- if n is not divisible by 3, then exactly one of (n - 1) and (n + 1) is divisible by 3, because every third integer is divisible by 3. therefore, the product (n - 1)(n + 1) contains a 3 in its prime factorization.
- thus, the overall prime factorization of (n - 1)(n + 1) contains three 2's and a 3.
- therefore, it is a multiple of 24.
- sufficient

answer = c

[rschunti]

I wanted to learn approach that is generic in nature and the same approach can be used for all types of scenario covering below type of questions. Pls can you help me in following:-
1) Pls verify whether my approach below is correct?
2) Pls recommend related Maths book that cover basic concepts and gives me apportunity to solve similar types of questions and also provide me solutions?
Condition 1 when n is not divisible by 2:-
n=2K+1 (k is integer)

(n-1)(n+1)=(n^2)-1=((2k+1)^2 -1)=4k(k+1)
If K=1 the value will be 8, if k=2 the value will be 24 etc.
Since we don't know the value of K hence not sufficient.

For condition 2 when n is not divided by 3:-
n=3k+1
(n-1)(n+1)=(n^2)-1=((3k+1)^2 -1)=3k(3k+2)
If K=1 the value will be 15, if k=2 the value will be 48 etc.Since we don't know the value of K hence not sufficient.

for both condition I and II.
since n is not divisible by both 2 and 3 then
n=6k+1
(n-1)(n+1)=(n^2)-1=((6k+1)^2 -1)=12k(3k+1)
For k=1,2,3,4 etc this number is multiple of 24 hence both I and II conditions are sufficient.

[RonPurewal]

see my response to your other thread, re: olympiad problems.

the materials you're looking for might be hard to find; most texts on elementary number theory, divisibility and primes, etc. will begin to digress well beyond the bounds of gmat problems.

in general, it's not such a great idea to learn too much theory. gmat problems almost always test very basic points of theory, spinning them in extremely clever ways that render them 'difficult' while still basic in terms of the underlying theory.

you should practice on as many gmat problems as possible: official problems (from gmatprep, og, and paperpreps) first, and then materials from prep companies if you exhaust all of those.

if you can produce the solution shown in this thread (with 'k'), then you know all the theory you'll ever have to know; you should concentrate on learning (and perhaps even memorizing) the many ways in which the gmat presents the same concepts.

[Grv]

There is a small gap in your solution - a set of numbers you dont account for.
If n is not divisibe by 3, then it can be either of these forms
n = 3k + 1 as well as n = 3k + 2.

If you only do, you are missing half the numbers like 8, 11 etc.

[RonPurewal]

There is a small gap in your solution - a set of numbers you dont account for.
If n is not divisibe by 3, then it can be either of these forms
n = 3k + 1 as well as n = 3k + 2.

If you only do, you are missing half the numbers like 8, 11 etc.

in my solution, no gap.

note the following:

one:
if you're referring to my treatment of statement (2), then, yes, i didn't consider all possibilities. this is because i didn't have to.
as soon as we find 2 examples that give contradictory answers, we have "insufficient", and we are done. to consider further examples at that point would be a complete waste of time.
takeaway:
once you're established "insufficient", do not bother testing additional cases!
the fact that n = 2 and n = 5 are both of the form (3k + 2) is random coincidence.

two:
if you look at the treatment of the 2 statements together, i have included both (3k + 1) and (3k + 2)-type cases in that treatment. unlike statement (2) alone, the combination of the 2 statements turns out to be sufficient, so this time i must consider all of the possibilities.
therefore, i do.

three:
note the following statement:

if n is not divisible by 3, then exactly one of (n - 1) and (n + 1) is divisible by 3

if n - 1 is divisible by 3, then n has the form 3k + 1.
if n + 1 is divisible by 3, then n has the form 3k + 2.
both have been considered.

[thanghnvn]

RON, ANYONE , please, help me, explain, why the expression can have 2*2*2 as factor.

[RonPurewal]

RON, ANYONE , please, help me, explain, why the expression can have 2*2*2 as factor.

did you read the second post in this thread?

if not, check it out -- the explanation is there.
if so, then please explain what you didn't understand.

also, note the plug-in explanation given in the earlier part of that post. the VAST majority of remainder DS problems can be solved by this sort of plugging; it's really not worth banging your head against theory on these kinds of problems unless you are a very skilled mathematician.

[sonygmat]

n=6k+1
(n-1)(n+1)=(n^2)-1=((6k+1)^2 -1)=12k(3k+1)
For k=1,2,3,4 etc this number is multiple of 24 hence both I and II conditions are sufficient.

I think there is a gap in this reasoning... if n is not divisible by 2 and not divisible by 3 then n=6k+1 or n=6k+5..

6k+5 is not tested therefore we can't be sure that both statements are sufficient!

Is my reasoning correct?

[RonPurewal]

n=6k+1
(n-1)(n+1)=(n^2)-1=((6k+1)^2 -1)=12k(3k+1)
For k=1,2,3,4 etc this number is multiple of 24 hence both I and II conditions are sufficient.

I think there is a gap in this reasoning... if n is not divisible by 2 and not divisible by 3 then n=6k+1 or n=6k+5..

6k+5 is not tested therefore we can't be sure that both statements are sufficient!

so, go ahead and test it:
(n - 1)(n + 1) = (6k + 4)(6k + 6)
= [2(3k + 2)][6(k + 1)]
= 12(3k + 2)(k + 1)
to prove that this expression is a multiple of 24, consider the even and odd cases. if k is even, then this expression is 12*even*odd; if k is odd, then it is 12*odd*even. in either of these cases, you wind up with 12 times an even number, so, overall, that's a multiple of 24.

at this point, i would once again like to refer readers back to the number plugging method above -- way, way more straightforward for almost all problems like this one.

[eorigbo]

Hey Ron,
Can you please explain how the remainder of 0/24 (the first number you plugged in) is 0?

[jlucero]

Zero is a weird number- technically it is divisible by any number and therefore has no remainder when divided by any number.
Numbers that are divisible by 2: 10, 8, 6, 4, 2, 0 (remainder when divided by 2 = 0)
Numbers that are divisible by 3: 12, 9, 6, 3, 0 (remainder when divided by 3 = 0)
Numbers that are divisible by 13: 52, 39, 26, 13, 0 (remainder when divided by 13 = 0)

Practical usage: I have zero dollars to split among my 24 friends- I hand out 0/24 = $0 to each friend. How much money do I have leftover? Nada. The same would be true dividing zero dollars amongst any number of friends- I would always have a leftover amount of $0 after giving away $0 to each of my friends.

[eorigbo]

Thanks for the clarification. 0 is weird indeed :)

[jnelson0612]

Thanks for the clarification. 0 is weird indeed :)

:-)

[Abhinav-]

(1)

moreover, since every other even number is a multiple of 4, one of those two factors is a multiple of 4. so the product (n - 1)(n + 1) contains one multiple of 2 and one multiple of 4, so it contains at least 2 x 2 x 2 = three 2's in its prime factorization.

answer = c

Hey Ron,

I'm in agreement with what you just said. However, how do we account for the fact this case: n=1, n-1=0 and n+1=2.
In this case there will only be one 2 in the prime factorisation of (n-1)(n+1), as opposed to all other cases where there will be three 2's. I was confused about this. Please clarify.

Thanks