Back to problem set

Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.

Problem 5

Show, for all positive integers n=1,2,…n = 1, 2,…, that 1414 divides 34n+2+52n+13^{4n + 2} + 5^{2n + 1}.

Hints

Hint #1

Rather than proving the statement directly, can you do it indirectly / incrementally?

Hint #2

See if you can use induction to prove the statement.

Solution

Expand to see solution; try solving it first or use the hints!

We can demonstrate this via induction. Recall that to prove something by induction, we have two steps:

  1. prove the base case
  2. prove the inductive case, e.g., if something is true for nn, it’s also true for n+1n+1

The above two steps let us claim that this is generally true for all nn of interest.

Let’s first consider the base case (n=1)(n = 1):

34n+2+52n+1=34+2+52+1=729+125=854=14⋅61 3^{4n + 2} + 5^{2n + 1} = 3^{4 + 2} + 5^{2 + 1} = 729 + 125 = 854 = 14 \cdot 61

Thus, 1414 divides that expression, so we have shown the base case.

Now let’s consider the inductive case:

  1. assume that 1414 divides 34n+2+52n+13^{4n + 2} + 5^{2n + 1}
  2. prove that 1414 divides 34(n+1)+2+52(n+1)+13^{4(n+1) + 2} + 5^{2(n+1) + 1}

Note that we can assume that:

34n+2+52n+1≡0mod  14(1) 3^{4n + 2} + 5^{2n + 1} \equiv 0 \mod 14 \qquad \text{(1)}

Let’s start with the second point:

34(n+1)+2+52(n+1)+1≡?0mod  14starting point34n+4+2+52n+2+1≡?0mod  14expand34⋅34n+2+52⋅52n+1≡?0mod  14factor to match starting point81⋅34n+2+25⋅52n+1≡?0mod  14simplify56⋅34n+2+25⋅34n+2+25⋅52n+1≡?0mod  14separate 81 into 25 and remainder56⋅34n+2+25⋅(34n+2+52n+1)≡?0mod  14factor out 2556⋅34n+2≡?0mod  14using eq. 10≡0mod  14since 56≡0mod  14 \begin{align*} 3^{4(n+1) + 2} + 5^{2(n+1) + 1} & \stackrel{?}{\equiv} 0 \mod 14 & \quad \text{starting point} \\ 3^{4n +4 + 2} + 5^{2n + 2 + 1} & \stackrel{?}{\equiv} 0 \mod 14 & \quad \text{expand} \\ 3^4 \cdot 3^{4n + 2} + 5^2 \cdot 5^{2n + 1} & \stackrel{?}{\equiv} 0 \mod 14 & \quad \text{factor to match starting point} \\ 81 \cdot 3^{4n + 2} + 25 \cdot 5^{2n + 1} & \stackrel{?}{\equiv} 0 \mod 14 & \quad \text{simplify} \\ 56 \cdot 3^{4n + 2} + 25 \cdot 3^{4n + 2} + 25 \cdot 5^{2n + 1} & \stackrel{?}{\equiv} 0 \mod 14 & \quad \text{separate $81$ into $25$ and remainder} \\ 56 \cdot 3^{4n + 2} + 25 \cdot (3^{4n + 2} + 5^{2n + 1}) & \stackrel{?}{\equiv} 0 \mod 14 & \quad \text{factor out $25$} \\ 56 \cdot 3^{4n + 2} & \stackrel{?}{\equiv} 0 \mod 14 & \quad \text{using eq. 1} \\ 0 & \equiv 0 \mod 14 & \quad \text{since $56 \equiv 0 \mod 14$} \\ \end{align*}

Above, we were able to first subtract the expression 25⋅(34n+2+52n+1)25 \cdot (3^{4n + 2} + 5^{2n + 1}) since it is divisible by 1414 and then similarly, 56⋅34n+256 \cdot 3^{4n + 2} since it is also divisible by 1414.

Since we have proven the inductive case, this completes the proof. ■\qquad \blacksquare