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

Question

How can I prove that

4^{n} + 15 n - 1 \equiv 0 (mod 9)

?

Answer 1

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

(4^{n + 1} + 15 (n + 1) - 1) - (4^{n} + 15 n - 1) = 3 (4^{n}) + 15

.
We see that the statement for

n + 1

is valid if

3 (4^{n}) + 15

is divisible by 9. But is it?
Let us check it again using mathematical induction. For

n = 1

, the number

3 (4^{n}) + 15

is clearly divisible by 9. So let us assume that

3 (4^{n}) + 15

is divisible by 9 for some n, and let us look at

3 (4^{n + 1}) + 15

. We see that the difference

(3 (4^{n + 1}) + 15) - (3 (4^{n}) + 15) = 9 (4^{n})

,
is divisible by 9, which means that

3 (4^{n + 1}) + 15

is divisible by 9, which means that

4^{n + 1} + 15 (n + 1) - 1

is divisible by 9.

Answer 2

Lets prove it mathematical induction.
Let

P (n) = 4^{n} + 15 n - 1

Lets first check if it is true for

n = 1

P (1) = 4 + 15 - 1 = 18

so

9 ∣ P (1)

So it is true for

n = 1

.
Now for induction step, we will assume it is true for

n = k

P (k) = 4^{k} + 15 k - 1

And we will check for

n = k + 1

P (k + 1) = 4^{k + 1} + 15 (k + 1) - 1

= {4.4}^{k} + 15 k + 15 - 1

= (1 + 3) {.4}^{k} + 15 k - 1 + 15

= 4^{k} + 15 k - 1 + {3.4}^{k} + 15

= P (k) + 3 (4^{k} + 5)

= P (k) + 3 (4^{k} - 1 + 1 + 5)

= P (k) + 3 (4^{k} - 1 + 6)

= P (k) + 3 (4^{k} - 1) + 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

(a - b) ∣ (a^{n} - b^{n})

so,

(4 - 1) = 3 ∣ (4^{n} - 1^{n})

3 (4^{k} - 1) \equiv 9 m (mod 9)

.
and

9 ∣ 18

so,

P (k + 1)

is true.
Answer:

9 ∣ = 4^{n} + 15 n - 1

.

Want to know more about Polynomial arithmetic?