# 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!

• Having got as far as $7\cdot5^{2n}=7\cdot4^{2n}$ and $2^{4n+1}=2\cdot4^{2n}$, can you not see a better way of continuing? – almagest May 4 '16 at 16:18
• @almagest I couldn't see it $7 \cdot 5^{2n} + 2^{4n+1} \equiv 4^{2n} \cdot 7 + 4^{2n} \cdot\ 2\ = 4^{2n} \cdot 9\ (9)$. Thanks. – jrs May 4 '16 at 17:10

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.

• thanks, it seems easier doing the proof by induction... yet I don't understand how you go from $7\cdot5^{2(n+1)}+2^{4(n+1)+1}$ to $16\cdot(\color\red{7\cdot5^{2n}+2^{4n+1}})+63\cdot5^{2n}$. I'm missing something, sorry! – jrs May 4 '16 at 17:30
• @Gio: Yes, I just cut it shorter to make the answer a little "cleaner". All you need is a few additional computations. I'm pretty sure that you can handle it, but just in case: $7\cdot5^{2(n+1)} = 7\cdot25\cdot5^{2n} = 175\cdot5^{2n} = (16\cdot7+63)\cdot5^{2n}$, and $2^{4(n+1)+1} = 2^{4n+1+4} = 2^{4n+1}\cdot2^{4} = 2^{4}\cdot2^{4n+1} = 16\cdot2^{4n+1}$. – barak manos May 4 '16 at 17:36