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

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.

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