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}$ .

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

Page

Toolbox

Search

2006 iTest Problems/Problem 14

Problem

Solution

See Also