I'm starting to solve some problems of congruence and integer division, so the exercise is quite simple but I'm not sure I'm on the right track. I need to prove that the following is true for all $n \in \Bbb N$:
$$9\ |\ 7 \cdot 5^{2n}+ 2^{4n+1}$$
This is what I have so far:
$$7 \cdot 5^{2n} + 2^{4n+1} \equiv 0 \ (9)$$
So I try to see what each side of the sum is congruent to: $7 \equiv -2 \ (9)$ and $5^{2n} \equiv 4^{2n} (9)$, hence: $7 \cdot 5^{2n} \equiv -2 \cdot 4^{2n} \ (9)$ and the left side is also congruent to: $-2 \cdot 4^{2n} \equiv 7^n \cdot -2 \ (9)$ which leaves me with:
$$7 \cdot 5^{2n} \equiv 7^n \cdot -2 \ (9)$$
As for the other side:
$$2^{4n+1} \equiv 7^{4n} \cdot\ 2\ (9)$$
Finally combining them:
$$7 \cdot 5^{2n} + 2^{4n+1} \equiv 7^n \cdot (-2) + 7^{4n} \cdot\ 2\ (9)$$
Am I right so far? Any hint on how to continue?
Thanks!
Answer
Alternative proof by induction.
First, show that this is true for $n=0$:
$7\cdot5^{2\cdot0}+2^{4\cdot0+1}=9$
Second, assume that this is true for $n$:
$7\cdot5^{2n}+2^{4n+1}=9k$
Third, prove that this is true for $n+1$:
$7\cdot5^{2(n+1)}+2^{4(n+1)+1}=$
$16\cdot(\color\red{7\cdot5^{2n}+2^{4n+1}})+63\cdot5^{2n}=$
$16\cdot\color\red{9k}+63\cdot5^{2n}=$
$9\cdot(16k+7\cdot5^{2n})$
Please note that the assumption is used only in the part marked red.
No comments:
Post a Comment