Question

Prove that 41 +1 5n-1 is divisible by 9.​

Answer 1

Answer:

How can I prove that 4^n +15n-1≡0 (mod 9)?

Lets prove it mathematical induction.

Let

[math]P(n)[/math]=4^n+15n-1

Lets first check if it is true for [math]n=1[/math]

[math]P(1)=4+15-1=18[/math]

so [math]9\mid P(1)\tag *{}[/math]

So it is true for [math]n=1.[/math]

Now for induction step, we will assume it is true for [math]n=k[/math]

[math]P(k)=4^k+15k-1\tag *{}[/math]

And we will check for [math]n=k+1[/math]

[math]P(k+1)=4^{k+1}+15(k+1)-1[/math]

[math]=4.4^k+15k+15-1[/math]

[math]=(1+3).4^k+15k-1+15[/math]

[math]=4^k+15k-1+3.4^k+15[/math]

[math]=P(k)+3(4^k+5)[/math]

[math]=P(k)+3(4^k-1+1+5)[/math]

[math]=P(k)+3(4^k-1+6)[/math]

[math]=P(k)+3(4^k-1)+18[/math]

Now, as per our assumption first term [math]P(k)[/math] is true. The term in the second bracket is divisible by [math]3[/math] which is evident from the fact

[math](a-b)\mid (a^n-b^n)[/math]

so, [math](4-1)=3\mid (4^n-1^n)[/math]

[math]3(4^k-1)\equiv 9m \pmod 9.[/math]

and [math]9\mid 18[/math]

so, [math]P(k+1) [/math] is true.

Hence, [math]9\mid =4^n+15n-1 \quad \blacksquare\tag *{}[/math]

mark mark me as billaint