Which of the following is NOT a factor of 3^16 - 1?

Question

(A) 2
(B) 5
(C) 24
(D) 40
(E) 41

ankushsambare · Answer

We need to find which is NOT a factor of 3^16 − 1.
Use the difference of squares repeatedly:
3^16 − 1 = (3^8 − 1)(3^8 + 1)
= (3^4 − 1)(3^4 + 1)(3^8 + 1)
= (3^2 − 1)(3^2 + 1)(3^4 + 1)(3^8 + 1)
Now evaluate:
 
 3^2 − 1 = 8 = 2^3 
 3^2 + 1 = 10 = 2 × 5 
 3^4 + 1 = 82 = 2 × 41  
So 3^16 − 1 is divisible by:
 
 2 
 5 
 41  
Now check 24.
Since 24 = 2^3 × 3, the number must be divisible by 3.
But:
3^16 − 1 ≡ −1 (mod 3)
so it is not divisible by 3.
Therefore, 24 cannot be a factor of 3^16 − 1.
 Answer: (C) 24.

Bunuel · Answer

GMATNinja Video Solution:

https://www.youtube.com/watch?v=cmpDVLHzT3w

nuwaaanda · Answer

I deduced this through a simple logic that if 3^16 is divisible by 3, then 3^16-1 is not divisible by 3. When you look at the options, only 24 is the option which needs 3^16-1 to be divisible by 3. Hence, it is definitely not divisible by 24. Is my approach correct or are there any gaps in this?

egmat · Answer

Hi nuwaaanda,

Your approach is correct, and it's a sharp one. You've spotted the cleanest possible path to this question, so let me confirm the logic and point out the one small thing worth nailing down so the reasoning is airtight.

Your core insight is right.3^16  is a multiple of  3 , so  3^16 - 1  sits one below a multiple of  3  - meaning it leaves a remainder of  2  when divided by  3 , and is  therefore  never divisible by  3 . Among the five choices, the only one that carries a factor of  3  is  24  (=  2^3  x  3 ). Since  3^16 - 1  has no factor of  3 , it can't be divisible by  24 . So  C  is the answer. That's exactly the right instinct.

The one gap to close.  Your shortcut quietly assumes two things - both true here, but worth verifying so you don't apply it blindly elsewhere:

-  24  is the only choice needing a factor of  3 . Check the others:  2 ,  5 , and  41  are primes with no  3  in them, and  40  =  2^3  x  5  has no  3  either. So yes,  24  is genuinely the unique choice that demands divisibility by  3 . Good.
- The question guarantees exactly one "NOT a factor." Because the stem promises a single correct answer, ruling out  24  on the factor-of- 3  test is enough - you don't have to prove the other four actually  are  factors. (They are, via  3^16 - 1  = (3^2 - 1)(3^2 + 1)(3^4 + 1)(3^8 + 1) =  8  x  10  x  82  x  6562 , which supplies the  2 ,  5 , and  41  - but you didn't need that to pick C.)

Quick habit to lock it in.  Whenever you use "this choice needs a factor the number doesn't have," do one fast scan:  is that factor unique to this choice?  If two choices needed a factor of  3 , the shortcut alone wouldn't separate them. Here it does, so your method is both valid and complete.

Answer: C

Which of the following is NOT a factor of 3^16 - 1?

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

Which of the following is NOT a factor of 3^16 - 1?

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