Problem Solving

M7MBA wrote:Which of the following is a factor of 1001^32−1

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

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

M7MBA wrote:Which of the following is a factor of 1001^32−1

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

Using the difference of squares, we have:

(1001^16 + 1)(1001^16 - 1)

(1001^16 + 1)(1001^8 - 1)(1001^8 +1)

(1001^16 + 1)(1001^4 - 1)(1001^4 + 1)(1001^8 +1)

(1001^16 + 1)(1001^2 - 1)(1001^2 + 1)(1001^4 + 1)(1001^8 +1)

(1001^16 + 1)(1001 - 1)(1001 + 1)(1001^2 + 1)(1001^4 + 1)(1001^8 +1)

We see that the two smallest factors in the above expression are 1001 - 1 = 1000 and 1001 + 1 = 1002.

1000 = 10^3 = 2^3 x 5^3

1002 = 2 x 501 = 2 x 3 x 167

Now, let's check the answer choices:

A) 768 = 3 x 256 = 3 x 2^8

We see that 1000 has three 2's, 1002 has one 2 and one 3. Upon further analysis, we can see that 1001^2 + 1, 1001^4 + 1, 1001^8 +1, and 1001^16 + 1 each will have at least one 2 since they are all even. Therefore, the 1001^32 - 1 must have at least eight 2's and one 3, and hence it's divisible by 768. In other words, 768 is a factor of 1001^32 - 1.

Answer: A