Mock AIME 1 2007-2008 Problems/Problem 12

From AoPSWiki

Problem 12

Let $d_1 = a^2 + 2^a + a \cdot 2^{(a+1)/2}$ and $d_2 = a^2 + 2^a - a \cdot 2^{(a+1)/2}$ . If $1 \le a \le 251$ , how many integral values of $a$ are there such that $d_1 \cdot d_2$ is a multiple of $5$ ?

Solution

$\begin{align*}[(a^2 + 2^a) + a \cdot 2^{(a+1)/2}][(a^2 + 2^a) - a \cdot 2^{(a+1)/2}] &= (a^2 + 2^a)^2 - a^2 \cdot 2^{a+1}\\&= a^4 + 2 \cdot a^42^{a} + 2^{2a} - a^2 \cdot 2^{a+1}\\&= a^4 + 2^{2a}\end{align*}$

(If you recall the reverse of Sophie Germain Identity with $a=a,\, b = 2^{(a-1)/2}$ , then you could have directly found the answer).

By Fermat's Little Theorem, we have that $a^{4} \equiv 1 \pmod{5}$ if $a \nmid 5$ and $a^{4} \equiv 0 \pmod{5}$ if $a | 5$ . Also, we note that by examining a couple of terms, $2^{2a} \equiv 4 \pmod{5}$ if $a \nmid 2$ and $2^{2a} \equiv 1 \pmod{5}$ if $a|2$ . Therefore, $a^{4} + 2^{2a} \equiv \{0,1\} + \{1,4\} \equiv \{0,1,2,4\} \pmod{5}$ With divisibility by $5$ achievable only if $a \nmid 2,5$ . There are $\frac{251-1}{2}+1 = 126$ odd numbers in the range given, and $\frac{245-5}{10}+1 = 25$ of those are divisible by $5$ , so the answer is $126 - 25 = \boxed{101}$ .

Mock AIME 1 2007-2008 (Problems, Source)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox

Mock AIME 1 2007-2008 Problems/Problem 12

From AoPSWiki

Problem 12

Solution

See also