Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 0 down vote accepted

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} $$

which is the same, except it's going from 'bottom up'.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.