Question

prove \(43 | 6^{n+2} + 7^{2n+1} \)

@ikram002p

Answer 1

Would it help if I convert it to \(\large 36\times6^n+7\times49^n\)?

Answer 2

(This kind of problem is challenging indeed I lyk dem :p)

Answer 3

(this is the first time i've never met this problem)

Answer 4

thats a good idea ! lets try to reduce further

Answer 5

\(\large 36\times2^n\times3^n+7\times7^n\times7^n\)? Am I going in the right way?

Answer 6

@kc_kennylau that actually makes things easier.

@ganeshie8 The best way to prove this is to use mathematical induction. Are you familiar with that technique?

Answer 7

49
--- leaves remainder 6
43

Answer 8

oh mathematical induction @ChristopherToni thanks

Answer 9

@ChristopherToni he's challenging us he actually knows how to do it

Answer 10

yes Chris :)

nooo i dont knw the solution yet, this problem came in my friend's exam today

Answer 11

\(\large 36\times6^n+7\times49^n \)

leaves same ramainder as

\(\large 36\times6^n+7\times 6^n \)

Answer 12

kc_kennlau i think u nailed it. we're done
but induction proof wud be beautiful to deduce if it doesnt take too many steps :)

Answer 13

@ganeshie8 thanks for your hint :)
so it goes: \[\hspace{11pt}\large43|6^{n+2}+7^{2n+1}\]\[\large=43|36\times6^n+7\times49^n\]\[\large=43|36\times6^n+7\times6^n\]\[\large=43|43\times6^n\]\(\large=0\)?

Thanks for your challenge i lyked it :)

Answer 14

looks neat !! thank you :)

Answer 15

it should be me who am thanking you :)
Thanks for training my brain :D

Answer 16

:)

induction :-
n = 1 lies in the set as 43 | 6^3 + 7^3
assume n is also in the set, lets prove n+1 hmm

Answer 17

il wait for Chris to complete... looks it can be tricky, we need to use congruences i feel

Answer 18

@ganeshie8 lol sorry I thought \(\large x|y\) wasn't a statement but in fact it is so I cannot use equal sign...

Answer 19

to hell wid notations lol i get wat u mean exactly :p

Answer 20

im going for lunch... wil get back in ~1 hour and try the induction... thanks friends :)

Answer 21

And I'll still be here waiting :)

Answer 22

By induction:

The base case is \(\large n=1\). So we see that
\[\large 6^{1+2} + 7^{2(1)+1} = 6^3 + 7^3 = 559 = 43\cdot 13\implies 43\mid 6^3+7^3.\]So the base case is proved.

Next suppose that for some \(\large k> 1\) that \(\large 43\mid 6^{k+2} + 7^{2k+1}\) which can be written as \(\large \color{red}{6^{k+2}+7^{2k+1} = 43m}\) for some \(\large m\in\Bbb{Z}\). We seek to show that
\[\large 43\mid 6^{(k+1)+2} + 7^{2(k+1)+1}=6^{k+3}+7^{2k+3}.\]
So, we note that
\[\large \begin{aligned} 6^{k+3} + 7^{2k+3} &= 6\cdot 6^{k+2} + 49\cdot 7^{2k+1}\\ &= 6\cdot 6^{k+2} + (43+6)\cdot 7^{2k+1}\\ &= 6\cdot 6^{k+2} + 6\cdot 7^{2k+1} + 43\cdot 7^{2k+1}\\ &= 6(\color{red}{6^{k+2}+7^{2k+1}}) + 43\cdot 7^{2k+1}\\ &= 6\cdot 43m + 43\cdot 7^{2k+1}\\ &= 43\underbrace{(6m+7^{2k+1})}_{\in\Bbb{Z}} \end{aligned} \]
Hence, \(\large 6^{k+3}+7^{2k+3}\) is a multiple of 43, which now implies that \(\large 43\mid 6^{k+3}+7^{2k+3}\).

Therefore, \(\large 43\mid 6^{n+2} + 7^{2n+1}\).

Does this make sense, guys?

Answer 23

Actually, on second thought, the base case is \(\large n=0\), since \(\large 6^2+7 = 43\) which clearly is divisible by 43.

Answer 24

that makes \(\Huge{\mbox{PERFECT}}\) sense :D

Answer 25

it can also solved by
using concept of congruence
7^n=6mod 43
6^n=6^n mod 43
6^2=36=-7 mod 43
6^2n=-7^n mod 43
-7 = 0 mod 43
-7.7^2n=6^2(6^n) mod 43
-7^(2n+1)=6^(n+2 ) mod 43

-(7^(2n+1)+6^(n+2 ))=43k #done ^_^

Answer 26

and the funny things was
it was mintion in the exam using induction is not allowed lol

Answer 27

Wow ! all 3 proofs look great !! xD
thanks @ikram002p @kc_kennylau @ChristopherToni =))

Answer 28

no problem at all :)

Answer 29

thank you for training my brain too :)