# Find all $n$ such that $3^{2n+1}+2^{n+2}$ is divisible by $7$ [duplicate]

Find all $n$ such that

$3^{2n+1}+2^{n+2}$ is divisible by $7$

So I am not allowed to use mods, as is a calculus question, I have tried by induction but can't get to prove that it works for $k+1$, by multiplying the equation by powers of $2$ and $3$.

Note that

$$\begin{split} 3^{2(k+1)+1} + 2^{(k+1)+2} &= 9\cdot 3^{2k+1} + 2\cdot 2^{k+2}\\ &= 7 \cdot 3^{2k+1} + 2 (3^{2k+1} + 2^{k+2}). \end{split}$$

• I have just done it Jan 8 '16 at 14:23

Let $A_n=3^{2n+1}+2^{n+2}$ then you will find that $A_{n+1}=11A_n-18A_{n-1}$

Rationale: If $u_n=A\alpha^n+B\beta^n$ it is easy to check that $u_{n+1}=(\alpha+\beta)u_n-\alpha\beta u_{n-1}$.

Set $\alpha = 3^2=9, \beta=2$.

You need two consecutive values to ensure the persistence of the factor $7$ (you could use $n=-1$ even though the value involves fractions), which makes it less attractive in some ways than the induction arguments with a single base case. However, this can also used to construct further examples of persistence, and is quick if you are doing multiple questions of the same type.

$3^{2n+1}+2^{n+2}$ is divisible by $7$ for all $n$:

$3^{2n+1}+2^{n+2}=\\ =3\cdot 9^n+4\cdot 2^n\\ =3\cdot (7+2)^n+(7-3)\cdot 2^n\\ =3(7a+2^n)+7\cdot2^n-3\cdot 2^n\\ =7(3a+2^n)$

where I have used the binomial theorem for getting $(7+2)^n=7a+2^n$.

• You can shorten it a bit. $$3\cdot 9^n+4\cdot 2^n=3\cdot (7+2)^n+4\cdot 2^n=3(7a+2^n)+4\cdot 2^n=7(3a+2^n)$$ Jan 8 '16 at 16:00
• @user236182, nicely spotted!
– lhf
Jan 8 '16 at 16:02

You're not allowed to use mod, but here's a proof using mod:

$$3^{2n+1}+2^{n+2}=3\cdot 9^{n}+4\cdot 2^n$$

$$\equiv 3\cdot 2^n+4\cdot 2^n\equiv 7\cdot 2^n\equiv 0\pmod{7}$$

Just another way:

Inductive hypothesis: $3^{2n+1} = 7k - 2^{n+2}$

Inductive step: $$3^{2n+3} + 2^{n+3} = 3^2 * 3^{2n+1} + 2 * 2^{n+2}$$

$=3^2(7k - 2^{n+2})+2*2^{n+2}$

$=7k(3^2) - 3^2*2^{n+2} + 2* 2^{n+2}$

$=7k(3^2) + 2^{n+2}(-3^2+2)$

$=7k(3^2) -7*(2^{n+2})$

Both terms are divisible by 7

• Thank you! What tool do you use to write on latex? Jan 8 '16 at 13:00
• Enter your equation within Dollar ($) signs. So start with a dollar sign, enter equation and end with a dollar sign. Jan 8 '16 at 13:06 • Great it seems easy enough Jan 8 '16 at 17:13 Little Hint: Note that from little Fermat's theorem that$2^6\equiv 1$and$3^6\equiv 1$. Then the remainders of$3\pmod 7$are $$3,2,6,4,5$$ while the remainders of$2\pmod 7$are $$2,4,1$$ If$n=1$,$2^3\equiv 1$and$3^3\equiv 6$...... • The OP said mod is not allowed. – lhf Jan 8 '16 at 15:47 1. Setting$n=1$, we get $$3^{2\cdot 1+1}+2^{1+2}=35$$ above number$35$is divisible by$7$hence it holds for$n=1$2. Assume the number$3^{2n+1}+2^{n+2}$is divisible by$7$for$n=k$then $$3^{2k+1}+2^{k+2}=7\lambda \tag 1$$ 3. Setting$n=k+1$, we get $$3^{2k+2+1}+2^{k+1+2}$$ $$=9\cdot 3^{2k+1}+2\cdot 2^{k+1}$$ $$=9\cdot 3^{2k+1}+9\cdot 2^{k+1}-7\cdot 2^{k+1}$$ $$=9(3^{2k+1}+2^{k+1})-7\cdot 2^{k+1}$$ setting the value from (1), $$=9(7\lambda)-7\cdot 2^{k+1}$$ $$=7(9\lambda-2^{k+1})$$ since,$(9\lambda-2^{k+1})$is some integer hence the number$7(9\lambda-2^{k+1})$is divisible by$7$hence the number$(3^{2n+1}+2^{n+1})$is divisible by$7$for all integers$n\ge 1\$