Induction: Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$

Question

Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$ for all $n \in \mathbb{N}$.

1. For $n=1$, $\Rightarrow 5^3 + 7^1 \Rightarrow 132 \mid 4$ (which is divisible by $4$)
2. Let us assume given equation holds true for $n = m$, $\Rightarrow 5^{3m} + 7^{2m-1} | 4$
3. Now for $n = m+1$,
   • $5^{3m+3} + 7^{2m+2-1}$
   • $5^{3m} \cdot 5^3 + 7^{2m-1} \cdot 7^2$
   • $5^{3m} \cdot 125 + 7^{2m-1} \cdot 49$

How do I go ahead from here? I am kind of stuck.

Answer 1

To complete your argument try to use the induction hypothesis. For example, write $$5^{3m} \cdot 125 + 7^{2m-1} \cdot 49 = (5^{3m} + 7^{2m-1}) + 5^{3m} \cdot 124 + 7^{2m-1} \cdot 48.$$

Now $4$ divides $5^{3m} + 7^{2m-1}$ by induction hypothesis, and $4$ divides $5^{3m} 124$ as $4$ divides $124$, and $4$ divides $7^{2m-1} \cdot 48$. Whence the sum of the three is also divisible by $4$ and you are done.

(This is basically the argument in the comments, but avoiding the modulo concept.)

Answer 2

HINT...Write $7^{2m-1}=4N-5^{3m},$ where$N\in\mathbb{Z}^+$, and substitute this into the expression you have, then factorise.

Answer 3

Use the binomial theorem: $$5^{3n} + 7^{2n-1}=(4+1)^{3n}+(8-1)^{2n-1}=4a+1^{3n}+8b+(-1)^{2n-1}=4c+1-1=4c$$

Answer 4

Let $M_{n}=5^{3n}+7^{2n-1}$, $n\in\mathbb{N}$. Now, as you well say, take $n=1$ then $M_{1}=5^{3}+7=132$ which is divisible by 4.

So, let us assume the equation holds true for $k$, i.e., $M_{k}=5^{3k}+7^{2k-1}$, and we try to prove that holds true for $k+1$. Therefore, $$M_{k+1}-M_{k}=(5^{3k+3}+7^{2k+1})-(5^{3k}+7^{2k-1})=5^{3k}(5^{3}-1)+7^{2k-1}(7^{2}-1)$$ $$=(7^{2}-1)(5^{3k}+7^{2k-1})+(5^{3}-7^{2})5^{3k}$$ $$\therefore M_{k+1}=M_{k}+48(5^{3k}+7^{2k-1})+76(5^{3k})$$ Where, each term is divisible for 4, and we're done.