Maths Olympiad Prep

Library / /10 of 32

Number theory Difficulty 5.3 AIME, harder Prove it Estonia

Prove that, for any natural number nn, either 32n−3n+1+3n−33^{2n} - 3^{n+1} + 3^n - 3 or 32n−3n+1+3n+13^{2n} - 3^{n+1} + 3^n + 1 is divisible by 32.

Solution

Note that 32n−3n+1+3n−3=(3n−3)(3n+1)3^{2n} - 3^{n+1} + 3^n - 3 = (3^n - 3)(3^n + 1).

If nn is odd then 3n−3=3(3n−1−1)=3(3n−12−1)(3n−12+1)3^n - 3 = 3(3^{n-1} - 1) = 3\left(3^{\frac{n-1}{2}} - 1\right)\left(3^{\frac{n-1}{2}} + 1\right).

As all powers of 33 are odd, 3n−12−13^{\frac{n-1}{2}} - 1 and 3n−12+13^{\frac{n-1}{2}} + 1 are consecutive even numbers. One of these numbers must be divisible by 44, whence their product is divisible by 88. Thus 8∣3n−38 \mid 3^n - 3, implying that 4∣3n+14 \mid 3^n + 1. Consequently, 32∣32n−3n+1+3n−332 \mid 3^{2n} - 3^{n+1} + 3^n - 3.

Assume now nn being even. Note that
32n−3n+1+3n+1=32n−3⋅3n+3n+1=(3n)2−2⋅3n+1=(3n−1)2. 3^{2n} - 3^{n+1} + 3^n + 1 = 3^{2n} - 3 \cdot 3^n + 3^n + 1 = (3^n)^2 - 2 \cdot 3^n + 1 = (3^n - 1)^2.
Similarly to the previous case, 3n−1=(3n2−1)(3n2+1)3^n - 1 = (3^{\frac{n}{2}} - 1)(3^{\frac{n}{2}} + 1) where factors in the r.h.s. are consecutive even numbers. Hence 8∣3n−18 \mid 3^n - 1, implying that 64∣32n−3n+1+3n+164 \mid 3^{2n} - 3^{n+1} + 3^n + 1. Consequently, 32∣32n−3n+1+3n+132 \mid 3^{2n} - 3^{n+1} + 3^n + 1.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.