Monday, 1 December 2014

elementary number theory - Prove that $9mid (4^n+15n-1)$ for all $ninmathbb N$



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 didn’t 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 hypothesis, 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 ones.



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!


Answer



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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...