2006 iTest Problems/Problem 14

Problem

Find $x$, where $x$ is the smallest positive integer such that $2^x$ leaves a remainder of $1$ when divided by $5$, $7$, and $31$.

$\text{(A) } 15 \quad \text{(B) } 20 \quad \text{(C) } 25 \quad \text{(D) } 30 \quad \text{(E) } 28 \quad \text{(F) } 32 \quad \text{(G) } 64 \quad \\ \text{(H) } 128 \quad \text{(I) } 45 \quad \text{(J) } 50 \quad \text{(K) } 60 \quad \text{(L) } 70 \quad \text{(M) } 80 \quad \text{(N) } \text{none of the above}\quad$

Solution

Note that $4$ is the smallest number where $2^x \equiv 1 \pmod{5}$, $3$ is the smallest number where $2^x \equiv 1 \pmod{7}$, and $5$ is the smallest number where $2^x \equiv 1 \pmod{31}$. Thus, $x$ must be a multiple of $3,4,5$. The lowest value of $x$ that is divisible by all three numbers is $\text{LCM}(3,4,5) = \boxed{\textbf{(K) } 60}$.

See Also

2006 iTest (Problems, Answer Key)
Preceded by:
Problem 13
Followed by:
Problem 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 U1 U2 U3 U4 U5 U6 U7 U8 U9 U10