# How can I prove that 4^{n}+15n-1 \equiv 0 (\mod 9)?

How can I prove that ${4}^{n}+15n-1\equiv 0\left(\text{mod}9\right)$?
You can still ask an expert for help

## Want to know more about Polynomial arithmetic?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Jonas Burt
By mathematical induction.
Clearly, the statement is true for $n=1$. Let it be valid for some natural number n. Is it then valid for $n+1$? Let us look at the difference
$\left({4}^{n+1}+15\left(n+1\right)-1\right)-\left({4}^{n}+15n-1\right)=3\left({4}^{n}\right)+15$.
We see that the statement for $n+1$ is valid if $3\left({4}^{n}\right)+15$ is divisible by 9. But is it?
Let us check it again using mathematical induction. For $n=1$, the number $3\left({4}^{n}\right)+15$ is clearly divisible by 9. So let us assume that $3\left({4}^{n}\right)+15$ is divisible by 9 for some n, and let us look at $3\left({4}^{n+1}\right)+15$. We see that the difference $\left(3\left({4}^{n+1}\right)+15\right)-\left(3\left({4}^{n}\right)+15\right)=9\left({4}^{n}\right)$,
is divisible by 9, which means that $3\left({4}^{n+1}\right)+15$ is divisible by 9, which means that ${4}^{n+1}+15\left(n+1\right)-1$ is divisible by 9.
###### Not exactly what you’re looking for?
Spandri3uv
Lets prove it mathematical induction.
Let $P\left(n\right)={4}^{n}+15n-1$
Lets first check if it is true for $n=1$
$P\left(1\right)=4+15-1=18$
so $9\mid P\left(1\right)$
So it is true for $n=1$.
Now for induction step, we will assume it is true for $n=k$
$P\left(k\right)={4}^{k}+15k-1$
And we will check for $n=k+1$
$P\left(k+1\right)={4}^{k+1}+15\left(k+1\right)-1$
$={4.4}^{k}+15k+15-1$
$=\left(1+3\right){.4}^{k}+15k-1+15$
$={4}^{k}+15k-1+{3.4}^{k}+15$
$=P\left(k\right)+3\left({4}^{k}+5\right)$
$=P\left(k\right)+3\left({4}^{k}-1+1+5\right)$
$=P\left(k\right)+3\left({4}^{k}-1+6\right)$
$=P\left(k\right)+3\left({4}^{k}-1\right)+18$
Now, as per our assumption first term P(k) is true. The term in the second bracket is divisible by 3 which is evident from the fact
$\left(a-b\right)\mid \left({a}^{n}-{b}^{n}\right)$
so, $\left(4-1\right)=3\mid \left({4}^{n}-{1}^{n}\right)$
$3\left({4}^{k}-1\right)\equiv 9m\left(\text{mod}9\right)$.
and $9\mid 18$
so, $P\left(k+1\right)$ is true.
Answer: $9\mid ={4}^{n}+15n-1$.