Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

First of all I would like to thank you for all the help you've given me so far.

Once again, I'm having some issues with a typical exam problem about divisibility. The problem says that:

Prove that $\forall n \in \mathbb{N}, \ 9\mid4^n + 15n -1$

I've tried using induction, but that didnt work. I've tried saying that:

$4^n + 15n-1 \equiv 0 \pmod{9}$. Therefore, I want to prove that $4^{n+1} + 15(n+1) -1 \equiv 0 \pmod{9}$.

I've prooved for $n=1$, it's $18\equiv 0 \pmod{9}$, which is OK.

But for the inductive step, I get:

$4\cdot4^n + 15n+15-1 \equiv 0 \pmod{9}$

And from there, I don't know where to replace my inductive hypotesis, and therefore, that's why I think induction is not the correct tool to use here. I guess I might use some tools of congruence or divisibility, but I'm not sure which are they.

I do realize that all $n\in \mathbb{N}/ \ 3 \ |\ n \Rightarrow 4^n \equiv 1 \pmod{9} \text{ and } 15n \equiv 0 \pmod{9}$. In that case, where 3 divides n, then I have prove that $4^n + 15n-1 \equiv 0 \pmod{9}$. But I don't know what to do with other natural numbers that are not divisible by 4, that is, all $n \in \mathbb{N} / n \equiv 1 \pmod{3} \text{ or } n \equiv 2 \pmod{3}$.

Any ideas? Thanks in advance!

share|improve this question
1  
Find the remainder of $4^{3k+1}$ modulo $9$, and that of $4^{3k+2}$. Since you already know $4^{3k} = 1 + 9\cdot x$, that's not difficult. –  Daniel Fischer Jul 15 '13 at 14:47
    
You can do a proof by induction here you just need to show the additional result that $4^k+5 = 0$ mod $3$. –  Cameron Williams Jul 15 '13 at 14:48
    
and what should I do with the $15n$? Thanks! –  pmartelletti Jul 15 '13 at 14:50

8 Answers 8

up vote 5 down vote accepted

By the Inductive Hypothesis, $4^n + 15n -1 \equiv 0$ so $4^n \equiv 1-15n$ and thus $$ 4^{n+1}+15(n+1)-1 = 4 \cdot 4^n + 15n + 14 \equiv 4 \cdot (1-15n) + 15n + 14 = 18 -45n \equiv 0 $$ since both $18$ and $45$ are divisible by 9.

share|improve this answer
    
Thanks! I liked this answer by induction... –  pmartelletti Jul 15 '13 at 14:53

You can use the fact that any natural number can be written in three forms : $n = 3k$ or $n = 3k+1$ or $n = 3k+2$.

In the case : $n = 3k$

$$ 4^n + 15 n - 1 = 64^k + 45 k -1 \equiv 0 \pmod{9} $$

And then you do the same for the other cases

share|improve this answer

You can do it by induction, skipping three steps. First check that it is correct for $n=1,2,3$. Then $4^{n+3}+15(n+1)-1=4^3\cdot 4^n+15n-45-1.$ As you have shown $4^3 \equiv 1 \pmod 9$ you are home.

share|improve this answer

Consider $$4\left(4^n+15n -1\right)-\left(4^{n+1} +15(n+1)-1\right) .$$

share|improve this answer

We don't really need induction as $$4^n+15n-1=(1+3)^n+15n-1$$ $$=1+\binom n13+\binom n23^2+\cdots+\binom n{n-1}3^{n-1}+3^n+15n-1$$ using Binomial Expansion

$$\implies 4^n+15n-1=18n+3^2\left(\binom n2+\cdots+\binom n{n-1}3^{n-3}+3^{n-2}\right)$$ which is clearly multiple of $9$ as we know Binomial coefficients are integers for positive integer $n$

share|improve this answer
    
@pmartelletti, how about this one? –  lab bhattacharjee Aug 5 '13 at 13:34

I'm going to do it by induction. First I need to prove that $4^k+5=0$ mod $3$.

Base case: $4^1+5 = 9$ and clearly $3$ divides this quantity.

Inductive hypothesis: $3|4^k+5$. Then $4^{k+1}+5 = 4*4^k+5 = 4^k+5+3*4^k$. Since $3|4^k+5$, it divides $4^{k+1}+5$ and we have shown the result.

Now we wish to prove the overall result that $3|4^k+15k-1$. Clearly the base case is true so we'll work on the inductive step. Suppose $3|4^k+15k-1$. Then $4^{k+1}+15(k+1)-1 = 4*4^k+15k+15-1 = (4^k+15k-1)+3(4^k+5)$. Since $3$ divides both of these terms individually, it divides their sum and we are done.

share|improve this answer

Note that $4^3\equiv1\pmod{9}$ and $15\cdot3\equiv0\pmod{9}$

Therefore, we only need to verify $4^n+15n\equiv1\pmod{9}$ for $n\in\{0,1,2\}$ since any $n$ is equivalent to one of these $\bmod{\,3}$. Since $\{1,19,46\}$ are all $\equiv1\pmod{9}$, the equation holds for all $n$.

share|improve this answer

Consider $$4^n=9q-15n+1;$$ So $$4.4^n+15n+15-1=4(9q-15n+1)+15n+14$$ And go on.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.