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,…$, that $14$ divides $3^{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:
- prove the base case
- prove the inductive case, e.g., if something is true for $n$, it’s also true for $n+1$
The above two steps let us claim that this is generally true for all $n$ of interest.
Let’s first consider the base case $(n = 1)$:
$$ 3^{4n + 2} + 5^{2n + 1} = 3^{4 + 2} + 5^{2 + 1} = 729 + 125 = 854 = 14 \cdot 61$$
Thus, $14$ divides that expression, so we have shown the base case.
Now let’s consider the inductive case:
- assume that $14$ divides $3^{4n + 2} + 5^{2n + 1}$
- prove that $14$ divides $3^{4(n+1) + 2} + 5^{2(n+1) + 1}$
Note that we can assume that:
$$ 3^{4n + 2} + 5^{2n + 1} \equiv 0 \mod 14 \qquad \text{(1)} $$
Let’s start with the second point:
$$ \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 \cdot (3^{4n + 2} + 5^{2n + 1})$ since it is divisible by $14$ and then similarly, $56 \cdot 3^{4n + 2}$ since it is also divisible by $14$.
Since we have proven the inductive case, this completes the proof. $\qquad \blacksquare$