2003 Pan African MO Problems/Problem 5

Revision as of 11:20, 15 January 2020 by Rockmanex3 (talk | contribs) (Solution to Problem 5 -- novice NT problem that requires precision)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

See Also

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