Wednesday, June 13, 2018

elementary number theory - Help with congruence and divisibility exercise



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...