Which number is a factor of 1001^32-1

Question

Which of the following is a factor of  1001^{32}-1

A. 768
B. 819
C. 826
D. 858
E. 924

DDB1981 · Accepted Answer

using prime factoring, we can break down 1001

1001 is a factor of 7 (700+280+21), and we're left with 143
143 is a factor of 11, and we're left with 13
13 is a factor of, well, 13

thus 1001^19 contains NINETEEN 7's, 11's and 13's, and is thus perfectly divisible by all of these
.... which means that 1001^19 -1 is NOT divisible by any of 7, 11, or 13

by process of elimination, B, C, and E are out, since they're all multiples of 7 (and therefore not valid divisors of our original number)
similarly, D is out since it's a multiple 11

--> A is the winner by POE, since it's the only surviving answer

Zarrolou · Answer

This is not a good question. What DDB1981 says is correct, the numbers must be co-prime => no common prime factor. So if one of the options has 7,11 or 13 as factor then the option is wrong.

However this is  not enough  to say that A is a factor.

Infact 768 is NOT a factor of  1001^{19}-1 . I calculated it  using this . Press mod to see the remainder.
This question has no correct answer, what is the source?

coolpintu · Answer

Hi,

I tried calculating it from the link provided by you and the no gets perfectly divided by 768.

The explanation provided is perfect. That is how we attack such question. Two consecutive numbers do not have any common factor. I am also for A.

Excellent explanation. I heard that 1001 is a number to be remembered as it is a product of 3 consecutive prime numbers 7, 11, 13 and is sometimes used in exams.

Posted from my mobile device

mau5 · Answer

Given  1001^{32}-1 --> The next consecutive integer is  1001^{32}  which can be factorized as  (7*11*13)^{32} . Note that any 2 consecutive integers are co-prime, i.e. they don't have any common factor other than 1. As 7,11, and 13 are all factors of  1001^{32} , thus  1001^{32}-1  will have NO common factors. From the given options, we have to look for a number, which is not a factor of any of the three primes. Only A satisfies the criteria.
A.

+1 to DDB1981

HKHR · Answer

Zarrolou,

Shouldnt we actually be concerned about  1001^{32}-1 . Why have you calculated for  1001^{19}-1  ? Thank you.

Bunuel · Answer

_________
It's a typo.

sam26can · Answer

Hi Bunnel,

Could you please comment if my understanding of the problem is correct.

a^n+b^n is divisible by a+b when n is even,and a^n-b^n is always divisible by a-b

〖1001〗^32-1=〖1001〗^32-1^32 is divisible by 1001+1=1002=2.3.167 and 1001-1=1000=2^3.5^3

From this limited information we know that 〖1001〗^32-1 is definitely a factor of 〖2.3.167.2〗^3.5^3 or any combinations of these integers

By implementing this information we can see that option B,C,D,E doesnot contain 167 as prime factor,there fore A must be an option as 768=(2^4.3).2^4

Thanks in advance

sanket1991 · Answer

using a^2 - b^2 = (a+b) (a-b)
we get 1000* 1002^5 = 2^3 * 5^3 * 2^5 * 3^5 * 167^5
now check which options are divisible by 2,3,5 or 167

A. 768
B. 819
C. 826
D. 858
E. 924

A has 3 * 2^8 clear winner
for B-E it will take 20 seconds more...hope this approach is clear

BrentGMATPrepNow · Answer

The key to answering this question is to recognize that 1001^32 − 1 is a  difference of squares 
And so it 1001^16 - 1
And 1001^18 - 1
etc

1001^32 − 1 = (1001^16 + 1)(1001^16 - 1)
= (1001^16 + 1)(1001^8 + 1)(1001^8 - 1)
= (1001^16 + 1)(1001^8 + 1)(1001^4 + 1)(1001^4 - 1)
= (1001^16 + 1)(1001^8 + 1)(1001^4 + 1)(1001^2 + 1)(1001^2 - 1)
= (1001^16 + 1)(1001^8 + 1)(1001^4 + 1)(1001^2 + 1)(1001 + 1)(1001 - 1)

Now let's evaluate some of the NICE parts.
= (1001^16 + 1)(1001^8 + 1)(1001^4 + 1)(1001^2 + 1)( 1002 )( 1000 
= (1001^16 + 1)(1001^8 + 1)(1001^4 + 1)(1001^2 + 1)( (2)(3)(167) )( (2)(2)(2)(3)(3)(3) )

Now check the answer choices....
A. 768 = (2)(2)(2)(2)(2)(2)(2)(2)(3) = (2^8)(3)
Hmmm, it  looks   like we might not have enough 2's in the factorization of 1001^16 - 1 in order for 768 to be a factor. 
However, if we recognize that (1001^16 + 1), (1001^8 + 1), (1001^4 + 1), and (1001of ^2 + 1) are all EVEN numbers, we can see that we have enough two's in the factorization of 1001^16 - 1 for 768 to be a factor.

Answer: A

Cheers,
Brent

vipsgmat · Answer

@bunuel please explain required your help on this question

Bunuel · Answer

Here is a solution: https://gmatclub.com/forum/which-number ... l#p2027263 Review it and let me know if anything specific is unclear.

Which number is a factor of 1001^32-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 number is a factor of 1001^32-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