2003 Pan African MO Problems/Problem 5

Problem

Find all positive integers $n$ such that $21$ divides $2^{2^n}+2^n+1$ .

Solution

In order for an integer to be divisible by $21$ , the integer must be divisible by both $3$ and $7$ .

For divisibility by 3, note that $2^n \equiv 1 \pmod{3}$ if $n$ is even and $2^n \equiv 2 \pmod{3}$ if $n$ is odd. Since $2^n$ is even for $n \ge 1$ , we must have $2^{2^n} \equiv 1 \pmod{3}$ for all values of $n$ . Therefore, $n$ must be an even number.

For divisibility by 7, because $2^3 \equiv 1 \pmod{7}$ , we must have $2^{3n} \equiv 1 \pmod{7}, 2^{3n+1} \equiv 2 \pmod{7}, 2^{3n+2} \equiv 4 \pmod{7}$ . Additionally, by trying small values of $n$ , we find that $2^{2^0} \equiv 2 \pmod{7}, 2^{2^1} \equiv 4 \pmod{7}, 2^{2^2} \equiv 2 \pmod{7}, 2^{2^3} \equiv 4 \pmod{7}$ .

Thus, we suspect that $2^{2^n} \equiv 2 \pmod{7}$ if $n$ is even and that $2^{2^n} \equiv 4 \pmod{7}$ if $n$ is odd. To prove this, we can use induction. For the base case, we know that $2^{2^0} \equiv 2 \pmod{7}$ and that $2^{2^1} \equiv 4 \pmod{7}$ . For the inductive step, assume that $2^{2^n} \equiv 4 \pmod{7}$ . By using properties of exponents and modular arithmetic, we have $2^{2^{n+1}} \equiv 2^{2 \cdot 2^n} \equiv (2^{2^n})^2 \equiv 2 \pmod{7}$ . Additionally, $2^{2^{n+2}} \equiv 2^{4 \cdot 2^n} \equiv (2^{2^n})^4 \equiv 4 \pmod{7}$ . The inductive step holds, so $2^{2^n} \equiv 2 \pmod{7}$ if $n$ is even and that $2^{2^n} \equiv 4 \pmod{7}$ if $n$ is odd.

Because we know that $n$ must be even, $2^{2^n} \equiv 2 \pmod{7}$ . Therefore, we must have $2^n \equiv 4 \pmod{7}$ , so $n \equiv 2 \pmod{3}$ . In summary, the integers $n$ that satisfy the original conditions are in the form $\boxed{n = 6n+2}$ .

2003 Pan African MO (Problems)
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All Pan African MO Problems and Solutions

Page

Toolbox

Search

2003 Pan African MO Problems/Problem 5

Problem

Solution

See Also