# Is this divisibility proof by induction correct/sufficient?

To show: 13 | $4^{2n+1}+3^{n+2}$

I used induction beginning successfully with n=0 (or n=1), then making the step to n+1:

An x exists so that $13x = 4^{2n+3}+3^{n+3}$

$13x = 16*4^{2n+1}+3*3^{n+2}$

$\frac{13}{3}x = \frac{16}{3}*4^{2n+1}+3^{n+3}$

$\frac{13}{3}x = \frac{13}{3}*4^{2n+1}+4^{2n+1}+3^{n+3}$

Here comes the actual question: Can I say that because of the premise the last two summands can be expressed as $13m$ with m being a natural number? Like this:

$\frac{13}{3}x = \frac{13}{3}*4^{2n+1}+13m$

$x = 4^{2n+1}+3m$ ... and that's a natural number.

Is that a valid proof?

-
You should write: an integer $x$ exists such that $13x = \ldots \iff 13x/3 = \ldots \iff x = \ldots\,$ because you need the $\Leftarrow$'s to conclude that $\,x\,$ is a solution of the original equation, i.e. in your proof, you need to go from bottom to top. –  Bill Dubuque Mar 24 '14 at 1:14

Yes, it seems to be correct. However, the person who would read the proof might be confused a little. Instead, you can re-write it differently, like $$\frac{4^{2n+3} + 3^{n+3}}{13} = \frac{13 \cdot 4^{2n+1} + 3\left(4^{2n+1} + 3^{n+1} \right)}{13} = \frac{13\cdot 4^{2n+1} + 3 \cdot 13m}{13} \in \mathbb{Z}$$