# 2006 iTest Problems/Problem 14

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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) 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
Invalid username
Login to AoPS