If the greatest common factor of positive integers n and m is 15, and the remainder when \((n+x)^{32}\) is divided by 15 is 1, which of the following CANNOT be the value of x?

A. 1
B. 4
C. 9
D. 11
E. 14


Are You Up For the Challenge: 700 Level Questions
_________________

I wd like to know if the following is correct

\(\frac{(n +11)^{32}}{15}\) = \(\frac{(15 +11)^{32}}{15}\)= \(\frac{(26)^{32}}{15}\)= \(\frac{(13^{32}\times 2^{32})}{15}\)= \(\frac{(13^{32}\times 2^{32})}{3 \times 5}\)

now Remainder of \(\frac{13^{32}}{3 }\) is 1

and the remainder of \(\frac{2^{32}}{5 }\) = \(\frac{4^{16}}{5 }\) is \((-1)^{16}\)

giving us the overall remainder of 1 for this answer option.

is the arithmetic correct?

Great analysis! But I think you can explain D and E better:

D: 11^2 = 121 = 15*8 + 1
E: 14^2 196 = 15 * 13 + 1

Since the GCF of n and m is 15, n must be a multiple of 15. If we expand (n + x)^32, every term in the expansion will have a factor of n except the last term, which is x^32. The terms that have a factor of n will be divisible by 15 (thus, the remainder is 0 when they are divided by 15). Therefore, the only way the remainder could be 1 when (n + x)^32 is divided by 15 would be if x^32 divided by 15 would yield a remainder of 1.

Now, let’s look at the choices.

A) 1

If x = 1, then 1^32 = 1 and when 1 is divided by 15, the remainder is 1.

B) 4

If x = 4, then 4^32 = (4^2)^16 = 16^16. Notice that when 16 is divided by 15, the remainder is 1. Therefore, when 16^16 is divided by 15, the remainder will be same as when 1^16 is divided by 15, and therefore, that remainder will be 1.

Let’s skip C for the moment and look at D and E first.

D) 11

Since 11 - 15 = -4, then x = 11 is equivalent to x = -4. However, since (-4)^32 = 4^32, then the remainder will be equal to the remainder when x = 4, which is 1.

E) 14

Similarly, since 14 - 15 = -1, then x = 14 is equivalent to x = -1. However, since (-1)^32 = 1^32, then the remainder will be equal to the remainder when x = 1, which is 1.

We have rejected choices A, B, D, and E. Therefore, the correct answer must be C.

Answer: C
_________________

SuryaNouliGMAT

Just to clarify n is not equal to 15, idea is to figure out different values for n given that the GCF (n,m) is 15.

Hope that makes sense.