Prove that for all $n \in \mathbb{N}$, either 3 or 13 divides $3^n + 13n^2 + 38$

Question

Let $a\in \{3,13\}.$ I'm having trouble with this proof. I know that

$$3^{n+1} + 13(n+1)^2 + 38 = (3^n + 13n^2 + 38) + (2\cdot 3^n + 26n + 13)$$

But I can't prove that $a \mid 2\cdot3^n + 26n + 13$. I know that 13 doesn't divide this because $13 \nmid 2\cdot3^n$. How can I prove that $3 \mid 26n + 13$?

Answer 1

For $n\ge1,$

$$f(n)=3^n+13n^2+38\equiv n^2-1\pmod3$$

So,

$$3\mid f(n)\iff n\equiv\pm1\iff3\nmid n\iff(n,3)=1$$

Again

$$3^n+13n^2+38\equiv3^n-1\pmod{13}$$ which holds true if $3\mid n$ as $3^3\equiv1\pmod{13}$

Answer 2

If $n\equiv1$ or $2\pmod3$ then $3^n+13n^2+38\equiv n^2+2\equiv0 \pmod 3$

because $3^n\equiv0$ and $13\equiv1$ and $38\equiv2 \pmod 3$, so $3|3^n+13n^2+38$.

If $n\equiv0\pmod3$ then $3^n+13n^2+38\equiv 1+12\equiv0\pmod { 13}$

because $3^3=27\equiv1 $ and $13\equiv0$ and $38\equiv12 \pmod {13}$, so $13|3^n+13n^2+38$.

Answer 3

You had the tag induction, so here's an answer by induction.

Base cases:

$n=0: 3^n+13n^2+38\equiv1+38\equiv39\equiv0\mod{13}$.

$n=1: 3^n+13n^2+38\equiv3+13+38\equiv54\equiv0\mod3$.

$n=2: 3^n+13n^2+38\equiv9+52+38\equiv99\equiv0\mod3$.

Inductive step:

$3^{n+3}+13(n+3)^2+38=3^n+13n^2+38+26\times3^n+78n+117$

$\equiv 3^n+13n^2+38 \mod 3$ or $13$.

Answer 4

Define $f(n) = 3^n + 13n^2 + 38$.

Using algebra it can be shown that for all $n \ge 0$ we have the following identities,

$\tag 1 f(n+1) = 3 f(n) -26 n^2 + 26 n -63$

$\tag 2 f(n+2) = 9 f(n) -104 n^2 + 52 n -252$

$\tag 3 f(n+3) = 27 f(n) -338 n^2 + 78 n -871 =$ $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \; \; \, \quad \quad 27 f(n) -13 (26 n^2 - 6 n + 67)$

By $\text{(3)}$, whenever $13 \mid f(n)$ it must also be true that $13 \mid f(n+3)$. Snce $f(0)) = 39$,

$\tag 4 13 \text{ divides every number in } \{f(0), f(3), f(6), \dots\}$

If we take $n = 3k$ in $\text{(1)}$ with $k \ge 0$, we can conclude that
[note that $3$ divides $3$, ${(3k)}^2$, $3k$ and $63$]

$\tag 5 3 \text{ divides every number in } \{f(1), f(4), f(7), \dots\}$

If we take $n = 3k$ in $\text{(2)}$ with $k \ge 0$, we can conclude that
[note that $3$ divides $9$, ${(3k)}^2$, $3k$ and $252$]

$\tag 6 3 \text{ divides every number in } \{f(2), f(5), f(8), \dots\}$