# Problem of the Day

If the greatest common factor of positive integers and is 15, and the remainder when is divided by 15 is 1, which of the following CANNOT be the value of ?

A. 1

B. 4

C. 9

D. 11

E. 14

### Solution

[latexpage]

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.