Library / Philippine Mathematical Olympiad /54 of 114

Philippine Mathematical Olympiad

Number theory Difficulty 5.3 AIME, harder Prove it Philippines

Problem:

Let $P = (3^{1} + 1)(3^{2} + 1)(3^{3} + 1) \ldots (3^{2020} + 1)$ . Find the largest value of the integer $n$ such that $2^{n}$ divides $P$ .

Solution

Solution:

If $k$ is even, then note that $3^{k} + 1 \equiv 2 \pmod{4}$ and so $2 \mid\mid 3^{k} + 1$ , i.e., $4 \nmid 3^{k} + 1$ .

On the other hand, if $k$ is odd, note that $3^{k} + 1 \equiv 4 \pmod{8}$ so $4 \mid\mid 3^{k} + 1$ , i.e., $4 \mid 3^{k} + 1$ but $8 \nmid 3^{k} + 1$ .

Thus the greatest value of $m$ for which $2^{m}$ divides $3^{k} + 1$ is $2$ if $k$ is odd, and $1$ if $k$ is even.

Summing up over $1 \leq k \leq 2020$ gives us $2 + 1 + \cdots + 2 + 1 = 1010(2 + 1) = 3030$ .

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.