2

Can someone give me a hint on how to solve this?

Prove that $3^{(3n+4)} + 7^{(2n+1)}$ is divisible by 11 for all natural numbers n.

So far I've got Base P(1): $3^{(3(1)+4)} + 7^{(2(1)+1)} = 2530$, which is divisible by 11 thus true

P(k): $3^{(3k+4)} + 7^{(2k+1)} = 11a$ for which $a$ $\in \mathbb{N}$

P(k+1): $3^{(3k+7)} + 7^{(2k+3)} = 11b$ for which $b$ $\in \mathbb{N}$

But i'm not sure how to continue from here in terms of breaking it down and proving the divisibility because of having 2 different indices. Appreciate any advice. Thank you.

BLAZE
  • 8,458
LucasCK
  • 101

4 Answers4

2

Your $P(k+1)$ is what you hope to be true, but you should avoid writing it as though it is fact.

What we do know is that $P(k)$ is true for some $k\geq 1$, and we hope to show that $P(k+1)$ follows.

You have $3^{(3k+4)} + 7^{(2k+1)} = 11a$ for some $a\in\mathbb{N}$

So, $3^{(3(k+1)+4)}+7^{(2(k+1)+1)} = 3^{3k+7} + 7^{2k+3} = 3^3\cdot 3^{3k+4} + 7^2\cdot 7^{2k+1}$

Now, notice that $3^3 = 27 = 2\cdot 11 + 5$

and that $7^2 = 49 = 4\cdot 11 + 5$

The result should follow soon after.

$$=(2\cdot 11 + 5)3^{3k+4} + (4\cdot 11+5)7^{2k+1} \\= 11(2\cdot 3^{3k+4}+4\cdot 7^{2k+1}) + 5\cdot (3^{3k+4}+7^{2k+1})\\=\dots$$

JMoravitz
  • 79,518
  • this is very clear and helpful, thank you! I have solved it but since 11 is already taken out of $2.3^{3k+4}+4.7^{2k+1}$, I can just leave it is that right as it is a multiple of 11? The other side I understand substitution. – LucasCK Oct 16 '15 at 18:14
  • 1
    It will wind up being $11\cdot (\text{messy stuff}) + 11\cdot a= 11(\text{messy stuff} + a)$. But, since the messy stuff is still an integer, this fits your needs to have it as $11b$ for some integer $b$. It could be rearranged a bit to make it more clear that you understand what is going on, but doesn't need to be simplified or changed much at all. – JMoravitz Oct 16 '15 at 18:17
2

HINT :

$$\begin{align}3^{3k+7}+7^{2k+3}&=27\cdot 3^{3k+4}+49\cdot 7^{2k+1}\\&=27\cdot 3^{3k+4}+(27+22)\cdot 7^{2k+1}\end{align}$$

mathlove
  • 139,939
2

P(k+1):$3^{3k+7} + 7^{2k+3} = 27 \cdot 3^{3k+4} + 49\cdot 7^{2k+1}\tag{1}$

From P(k): $3^{3k+4} = \color{blue}{11a - 7^{2k+1}}$

So $(1)$ becomes

$27(\color{blue}{11a - 7^{2k+1}})+49\cdot 7^{2k+1}=27\cdot 11a -27\cdot 7^{2k+1}+ 49\cdot 7^{2k+1}=27\cdot 11a +2\cdot 11\cdot 7^{2k+1}=\color{red}{11}(27a+2\cdot 7^{2k+1})$

Hence $3^{3n+4} + 7^{2n+1}$ is a multiple of $\color{red}{11} \space\forall \space n\in \mathbb{N}$

QED

BLAZE
  • 8,458
1

Modulo $11$ we have $3^{3n+4}+7^{2n+1}\equiv 3^{3n}.3^4+7^{2n}.7\equiv 3^{3n}.81+7^{2n}.7\equiv 3^{3n}.4+7^{2n}.(-4)\equiv 4(3^{3n}-7^{2n})\equiv 4( 27^n-49^n)\equiv 4(5^n-5^n)=0.$

DanielWainfleet
  • 57,985