M28-26

Question

If  n  is a non-negative integer and the remainder when  3^n  is divided by 4 is a multiple of 3, then which of the following must be true?
 
I.  n^2  divided by 4 yields the reminder of 1
 
II.  (-2)^n  is less than 0
 
III.  n  is a prime number

A.  I  only
B.  II  only
C.  III  only
D.  I  and  II  only
E.  II  and  III  only

Bunuel · Accepted Answer

Official Solution:

If  n  is a non-negative integer and the remainder when  3^n  is divided by 4 is a multiple of 3, then which of the following must be true?
 
I.  n^2  divided by 4 yields the reminder of 1
 
II.  (-2)^n  is less than 0
 
III.  n  is a prime number

A.  I  only
B.  II  only
C.  III  only
D.  I  and  II  only
E.  II  and  III  only

Let's explore the possible remainders obtained by dividing  3^n  by 4 for different values of  n :
 
 3^0=1 .The remainder when 1 is divided by 4 is 1, which is NOT a multiple of 3;
 
 3^1=3 . The remainder when 3 is divided by 4 is 3, which is a multiple of 3;
 
 3^2=9 . The remainder when 9 is divided by 4 is 1, which is NOT a multiple of 3;
 
 3^3=27 . The remainder when 27 is divided by 4 is 3, which is a multiple of 3;
 
...
 
Since we are told that the remainder when  3^n  divided by 4 gives a multiple of 3, then we can conclude that   n  is odd .
 
I.  n^2  divided by 4 yields the reminder of 1. Since  n  is odd, then  n^2=odd^2=(2k+1)^2=4k+4k+1 , which when divided by 4 yields the reminder of 1. Hence, this statement is true.
 
II.  (-2)^n  is less than 0. 
 
Since  n  is odd, then  (-2)^n=(-2)^{odd} . Negative number in odd power is always negative. Hence, this statement is also true.
 
III.  n  is a prime number. 
 
Since not all odd number are primes, then this option is not necessarily true.

Answer: D

Boycot · Answer

My apologies for a simple question, but how is it possible to prove that odd^2 divided by 4 always yields the reminder of 1?

Is it correct based on (o/2)*(o/2)=(q*2+1)(q*2+1), so after multiplication we can conclude that R=1

Or based on (odd^2-1+1)/4, where odd^2-1 is always divisible by 4

Or is it a rule that i missed?

My concern aroused cause originally i came to the conclusion base on several numbers substitution.

Bunuel · Answer

An odd number can be represented as 2k + 1 --> (2k + 1)^2 = 4k^2 + 4k + 1 --> first two terms are divisible by 4, so the remainder would come only from the third term --> 1 divided by 4 yields the remainder of 1.

Check it with numbers:
1^2 = 1 yields the remainder of 1 when divided by 4;
3^2 = 9 yields the remainder of 1 when divided by 4;
5^2 = 25 yields the remainder of 1 when divided by 4;
...

Hope it's clear.

Bunuel · Answer

I have edited the question and the solution by adding more details to enhance its clarity. I hope it is now easier to understand.

Amrita01 · Answer

I think this is a  high-quality  question and I agree with explanation. I have a doubt that 'n must be odd since the remainder is a multiple of 3'. Is that deduced by taking examples or how to prove it

Bunuel · Answer

Please review this:

Let's explore the possible remainders obtained by dividing  3^n  by 4 for different values of  n :

3^0=1 .The remainder when 1 is divided by 4 is 1, which is NOT a multiple of 3;

3^1=3 . The remainder when 3 is divided by 4 is 3, which is a multiple of 3;  THE POWER OF 3 IS 1, WHICH IS ODD.

3^2=9 . The remainder when 9 is divided by 4 is 1, which is NOT a multiple of 3;

3^3=27 . The remainder when 27 is divided by 4 is 3, which is a multiple of 3;  THE POWER OF 3 IS 3, WHICH IS ODD.

...

Since we are told that the remainder when  3^n  divided by 4 gives a multiple of 3 , then we can conclude that   n  is odd .

Hope it helps.

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

M28-26

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards