Maths Olympiad Prep

Library / /6 of 27

Number theory Difficulty 5.0 AIME, harder Prove it Croatia

Prove that 22n+2+42^{2^{n+2}} + 4 is a multiple of 1010 for any positive integer nn. (Tamara Srnec)

Solution

Let us consider 22n+2+42^{2^{n+2}} + 4 modulo 1010.

First, note that 22n+22^{2^{n+2}} is a very large power of 22. Let's analyze the last digit of 2k2^k for large kk.

The last digit of powers of 22 cycles every 44:

kk2k2^kLast digit
122
244
388
4166
5322
6644
71288
82566

So, the last digit of 2k2^k depends on kmod4k \bmod 4:
- If k1(mod4)k \equiv 1 \pmod{4}, last digit is 22.
- If k2(mod4)k \equiv 2 \pmod{4}, last digit is 44.
- If k3(mod4)k \equiv 3 \pmod{4}, last digit is 88.
- If k0(mod4)k \equiv 0 \pmod{4}, last digit is 66.

Now, 2n+22^{n+2} is always even for n1n \geq 1 (since n+23n+2 \geq 3), so 2n+282^{n+2} \geq 8.

But more importantly, 2n+22^{n+2} is divisible by 44 for n1n \geq 1:
- 2n+2=42n2^{n+2} = 4 \cdot 2^{n}, so 2n+20(mod4)2^{n+2} \equiv 0 \pmod{4}.

Therefore, 22n+22^{2^{n+2}} is a power of 22 where the exponent is divisible by 44.

From the table above, if k0(mod4)k \equiv 0 \pmod{4}, the last digit of 2k2^k is 66.

Thus, 22n+22^{2^{n+2}} ends with 66 for any positive integer nn.

Therefore,
22n+2+4 2^{2^{n+2}} + 4
has last digit 6+4=106 + 4 = 10, so ends with 00.

Thus, 22n+2+42^{2^{n+2}} + 4 is divisible by 1010 for any positive integer nn.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.