Problem of the Day

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

Reveal Answer


C. 9

See the Solution



If the greatest common factor of $n$ and $m$ is 15, then $n$ is a multiple of 15. Thus, we can interpret $x$ as the remainder of $n+x$ when it is divided by 15. If an integer, $a$, has a remainder, $r$, with respect to some divisor, $d$, $a^y$ will have the same remainder as $r^y$ with respect to divisor, $d$. If $x=1$, $(n+1)^{32}$ has the same remainder as $1^{32}$, which is 1. For $x=4$, $(n+4)^{32}$= $((n+4)^2)^{16}$. $4^2=16$, which has a remainder of 1, so $(n+4)^{32}$ would have a remainder of 1 with respect to 15. Similar arguments can be made for $x=14$ and  and $x=11$ because this is equivalent to having remainders of $-1$ and $-4$ respectively, which would work out the same as $x=1$ and $x=4$, because 32 is an even exponent. $x=9$ will never produce a remainder of 1, so it is the answer.

Comments are closed.