Remainder

[goelmohit2002]

N is an integer, r is the remainder when ((N-1)*(N+1)) is divided by 24. What is the value of r ?

1) N is not a multiple of 2.
2) N is not a multiple of 3.

[scoobydooby]

1)N not multiple of 2
=>N=1, 0*3/24 remainder 0
=>N=3, 2*4/24 remainder 8
not sufficient

2) N not multiple of 3
=>N=2, 1*3/24 remainder 3
=>N=5, 4*6/24 remainder 0

not sufficient

together, N not a multiple of 2 and 3
=>N=1,5, 7, 11.. leave a remainder of 0

N=1, (N-1)(N+1)/24=0*2/24 remainder 0
N=5, (N-1)(N+1)/24= 4*6/24 remainder 0

sufficient, hence C

[goelmohit2002]

1)N not multiple of 2
=>N=1, 0*3/24 remainder 0
=>N=3, 2*4/24 remainder 8
not sufficient

2) N not multiple of 3
=>N=2, 1*3/24 remainder 3
=>N=5, 4*6/24 remainder 0

not sufficient

together, N not a multiple of 2 and 3
=>N=1,5, 7, 11.. leave a remainder of 0

N=1, (N-1)(N+1)/24=0*2/24 remainder 0
N=5, (N-1)(N+1)/24= 4*6/24 remainder 0

sufficient, hence C

Thanks SD.....

Is there a way to solve without using numbers ? Beacuse here calculation is simple, so we did the same....but what if calculation involves very complex numbers.....

Is there a general solution for the same ?

[DanaJ]

For the sake of brevity, let's assume (N-1)(N+1) = x.

1. If N is not a multiple of 2, then both N-1 and N+1 are going to be even, so x will be the product of two even numbers, making it a multiple of 4. However, this is not enough to establish the remainder of x/24. Consider x = 16 and x = 20: we get different results for the two values.

2. If N is not a multiple of 3, then either N-1 or N+1 will be a multiple of 3 (there's that age-old rule that out of three consecutive numbers, one of them is a multiple of 3). This doesn't help with 24, however. Take x = 6 and x = 9: they are both divisible by 3, but yield different remainders when divided by 24.

If you put both statements together you get that N is not even and not a multiple of 3. The LCM f 2 and 3 is 6 and all numbers can be expressed according to the remainder they yield when divided by 6 like so:

6k - can't be N, since N is not div by 2
6k + 1
6k + 2 - can't be N, since N is not even
6k + 3 - can't be N, since N is not div by 3
6k + 4 - can't be N, since N is not even
6k + 5

So, out of all the numbers out there, N can be either 6k + 1 or 6k + 5. But watch what happens to x:
a. N = 6k + 1
N - 1 = 6k
N + 1 = 6k + 2

x = 6k(6k + 2) = 12k(3k + 1) - x is obviously divisible by 12, but it will also be divisible by 24. This is because no matter what k is, 3k + 1 will be the opposite of it: if k is even, then 3k + 1 will be odd.

You may wonder how could this be: well, 3k + 1 = (k + 1) + 2k. Adding an even number (2k) to another number (k + 1) will always make the sum even or odd depending on k + 1.

So k(3k + 1) = 2p (where p is an integer) will always be even, since one of its components will be even and the other will be odd.

Finally, x can be rewritten as x = 12 * 2 * p = 24p. x is divisible by 24.


b. N = 6k + 5
N - 1 = 6k + 4
N + 1 = 6(k + 1)

x = (6k + 4)*6*(k + 1) = 12(3k + 2)(k + 1). The demonstration why (3k + 2)(k + 1) will always be even is similar to the one above, since in this case we have (k + 1) and (3k + 1) + 1 instead of k and 3k + 1 respectively.

So again x = 12 * 2 * r = 24r. x is divisible by 24.


IMHO, really, really hard demonstration, or at least the way it look a it. I'm really curious whether someone could come up with a faster way of doing this except number picking.

[Ian Stewart]

I posted a solution here:

www.beatthegmat.com/gmat-prep-remainder ... 16996.html

[goelmohit2002]

I posted a solution here:

www.beatthegmat.com/gmat-prep-remainder ... 16996.html

Thanks Ian.

Can you please tell....how to solve the same in case statement 2 would have been "4 is not a factor of N"...

[goelmohit2002]

For the sake of brevity, let's assume (N-1)(N+1) = x.

1. If N is not a multiple of 2, then both N-1 and N+1 are going to be even, so x will be the product of two even numbers, making it a multiple of 4. However, this is not enough to establish the remainder of x/24. Consider x = 16 and x = 20: we get different results for the two values.

2. If N is not a multiple of 3, then either N-1 or N+1 will be a multiple of 3 (there's that age-old rule that out of three consecutive numbers, one of them is a multiple of 3). This doesn't help with 24, however. Take x = 6 and x = 9: they are both divisible by 3, but yield different remainders when divided by 24.

If you put both statements together you get that N is not even and not a multiple of 3. The LCM f 2 and 3 is 6 and all numbers can be expressed according to the remainder they yield when divided by 6 like so:

6k - can't be N, since N is not div by 2
6k + 1
6k + 2 - can't be N, since N is not even
6k + 3 - can't be N, since N is not div by 3
6k + 4 - can't be N, since N is not even
6k + 5

So, out of all the numbers out there, N can be either 6k + 1 or 6k + 5. But watch what happens to x:
a. N = 6k + 1
N - 1 = 6k
N + 1 = 6k + 2

x = 6k(6k + 2) = 12k(3k + 1) - x is obviously divisible by 12, but it will also be divisible by 24. This is because no matter what k is, 3k + 1 will be the opposite of it: if k is even, then 3k + 1 will be odd.

You may wonder how could this be: well, 3k + 1 = (k + 1) + 2k. Adding an even number (2k) to another number (k + 1) will always make the sum even or odd depending on k + 1.

So k(3k + 1) = 2p (where p is an integer) will always be even, since one of its components will be even and the other will be odd.

Finally, x can be rewritten as x = 12 * 2 * p = 24p. x is divisible by 24.


b. N = 6k + 5
N - 1 = 6k + 4
N + 1 = 6(k + 1)

x = (6k + 4)*6*(k + 1) = 12(3k + 2)(k + 1). The demonstration why (3k + 2)(k + 1) will always be even is similar to the one above, since in this case we have (k + 1) and (3k + 1) + 1 instead of k and 3k + 1 respectively.

So again x = 12 * 2 * r = 24r. x is divisible by 24.


IMHO, really, really hard demonstration, or at least the way it look a it. I'm really curious whether someone could come up with a faster way of doing this except number picking.

Awesome DanaJ....real awesome explanation!!!!

Can someone tell if there is someother easier general approach as compared to the general approach suggested by DanaJ ?

Thanks
Mohit

[DanaJ]

I think Ian's approach was a much better/faster one...

[goelmohit2002]

I think Ian's approach was a much better/faster one...

Yes, but what if statement #2 would have been ""4 is not a factor of N"...then how to solve.....

[DanaJ]

Well, the fact that 4 is not a factor of N would not add much value if we consider both statements, since if a number is not even (statement 1: 2 is not a factor of N), then it will surely NOT BE a multiple of 4.

You could use the same approach as above: the LCM of 2 and 4 is 4, so every number can be written as:

4k - out since it's even
4k + 1
4k + 2 - out since it's even
4k + 3

So N can only be 4k + 1 or 4k + 3. Split it up into cases as above:

a. N = 4k + 1
N -1 = 4k
N + 1 = 4k + 2

x = 4k(4k+2)= 8k(2k +1) - here, you can't go any further, since 2k + 1 will always be odd, no matter what k is.

It's largely the same thing with b. N = 4k + 3.

Note that you won't probably see such a question on the real thing. They'd pick numbers like 2 and 3 or 2 and 5, that have GCD 1.

[goelmohit2002]

Thanks DanaJ

[enniguy]

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) 2 is not a factor of "n"
(2) 3 is not a factor of "n"

(1) says that n is odd. Thus n-1 and n+1 are both even. In fact, one of them must be divisible by 4, because every second even number is divisible by 4. So from (1) we know that (n-1)(n+1) is divisible by 8.

(2) says that n is not divisible by 3. Notice that n-1, n, and n+1 are three consecutive integers. If you have any three consecutive integers, exactly one of them must be divisible by 3. So if n is not divisible by 3, either n-1 or n+1 is.

Using both (1) and (2) together, we know (n-1)(n+1) is divisible by both 3 and 8, and therefore by 24.

In Ian's explanation, I have a question.

If we consider n to be 1, then n-1 = 0 and n+1 = 2. None of these 2 consecutive even integers are divisible by 4. How can we assume that for statement 1?

Am I missing something?

[goelmohit2002]

In Ian's explanation, I have a question.

If we consider n to be 1, then n-1 = 0 and n+1 = 2. None of these 2 consecutive even integers are divisible by 4. How can we assume that for statement 1?

Am I missing something?

0 is divisile by every integer including 4...since it leaves remainder 0.....I guess this might help.

[vikram_k51]

N is an integer, r is the remainder when ((N-1)*(N+1)) is divided by 24. What is the value of r ?

1) N is not a multiple of 2.
2) N is not a multiple of 3.

Will be C.

For any odd Integer greater than 3 the rem is 0.
Now if N is not a multiple of 3 then N is any odd integer greater than 3 which gives 0 as remainder.