For a nonnegative integer n, if the remainder is 1 when 2^n

Question

For a nonnegative integer n, if the remainder is 1 when 2^n is divided by 3, then which of the following must be true?

I. n is greater than zero.
II. 3^n = (-3)^n
III. √2^n is an integer.

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

Bunuel · Accepted Answer

Please check the questions when posting.

Given:  n=integer\geq{0}  and  2^n=3q+1 , for some non-negative integer  q :

If  n=0=even  -->  2^0=1  --> remainder upon division 1 by 3 is 1 - OK;
If  n=1=odd  -->  2^1=2  --> remainder upon division 2 by 3 is 2 - not OK;
If  n=2=even  -->  2^2=4  --> remainder upon division 4 by 3 is 1 - OK;
If  n=3=odd  -->  2^3=8  --> remainder upon division 8 by 3 is 2 - not OK;
...

So we can see the pattern of reminders 1-2-1-2-.... --> given condition that the remainder is 1 when  2^n  is divided by 3 holds true when  n=even . So  n  must be non-negative even number: 0, 2, 4, ...

I.  n  is greater than zero --> not necessarily true, as  n  can be zero;
II.  3^n = (-3)^n  --> as  n  is even then this statement is always true;
III.  \sqrt{2}^n=integer  --> as  n  is non-negative even number then this statement is always true.

Answer: E (II and III only).

banksy · Answer

Thank you, Bunuel! I checked a lot of sources, but your explanation is the best, as usual!=)

lionot · Answer

Bunuel, Your explanation is always the BEST! THANK U.......

rggoel9 · Answer

just a question on this is it (√2)^n or (√2^n).

Just have some confusion on this.

Bunuel · Answer

They are the same:  (\sqrt{2})^n=\sqrt{2^n} .

stevie1111 · Answer

Tried solving using the 1st post and got mightily confused....Thx Bunuel!!

Bunuel · Answer

Bumping for review and further discussion*. Get a kudos point for an alternative solution!

*New project from GMAT Club!!! Check HERE

Theory on remainders problems: remainders-144665.html

All DS remainders problems to practice: search.php?search_id=tag&tag_id=198
All PS remainders problems to practice: search.php?search_id=tag&tag_id=199

mau5 · Answer

We know that  x^n-a^n  is divisible by (x-a) AND (x+a) ONLY when n is an even integer.

Now , from the given problem,  2^n  = 3q+1-->  \frac{2^n-1^n}{3}  = q(An integer)-->  \frac{2^n-1^n}{(2+1)}  = q. 
Thus, n HAS to be even. Now, only options II and III stand for n= even.
E.

prateekbhatt · Answer

Yes. Typo edited. Thank you.

\sqrt{2}^0  equals 1 or  \sqrt{2}  its self

Bunuel · Answer

\sqrt{2}^0=1  .

vitaliyGMAT · Answer

We have following question:

\frac{2^n}{3} = 1 (mod 3)

2 = -1 (mod 3)  and our question boils down to the following:

\frac{(-1)^n}{3} = \frac{1}{3}

This is only possible when n is even. N=0, 2, 4 …..

I. n is greater than zero. No. n can be equal to 0 because 0 is even
II. 3^n = (-3)^n True when n is even
III. √2^n is an integer. Also true when n is even.  \sqrt{2^0} = \sqrt{1}= 1

Options II and III only.

Answer E.

KarishmaB · Answer

n is nonnegative integer - Immediately think of n = 0
When 2^0 = 1 is divided by 3, remainder is 1.
When n = 1, 2^1 divided by 3 gives remainder 2.
When n = 2, 2^2 = 4 divided by 3 gives remainder 1.

When a number is divided by 3, the remainder must be 0/1/2.
So here is the pattern: 2^n divided by 3 will not give 0 as remainder since 2^n has no 3s in it.
2^n will give remainder 1 when n is even.
2^n will give remainder 2 when n is odd.

Since we want the remainder to be 1, n MUST be even.

I. n is greater than zero.
Not necessary since n can be 0.

II. 3^n = (-3)^n
Since n is even, this must be true.

III. √2^n is an integer.
n is 0/2/4/... - In each case, this will be an integer.

Answer (E)

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.

For a nonnegative integer n, if the remainder is 1 when 2^n

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

GMAT Problem Solving (PS) Questions

For a nonnegative integer n, if the remainder is 1 when 2^n

Prep Toolkit

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