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.

Prove that $2^n3^{2n} -1$ is always divisible by $17$.

I am very new to proofs and i was considering using proof by induction but I am not sure how to. I know you have to start by verifying the statement is true for the integer 1 but I dont know where to go from there.

share|improve this question
2  
Welcome to Math.SE! Please, consider updating your question to include some information about what you've tried and where you're getting stuck. Questions of this form "Prove..." tend to not get any positive response without some sign of effort by the poster; update it, though, and we'll be happy to help! –  Nicholas R. Peterson Sep 8 '13 at 23:03
    
I am very new to proofs and i was considering using proof by induction but I am not sure how to. I know you have to start by verifying the statement is true for the integer 1 but I dont know where to go from there. –  Suzanne Frank Sep 8 '13 at 23:07
1  
@SuzanneFrank If this is homework please also include that (homework) tag in your posting. Thanks –  Rustyn Sep 8 '13 at 23:12
    
Whatever you have tried, it is a good idea to incorporate your work in the question, so users see where you are stuck in your attempt to solve it using induction. –  Stefan Hamcke Sep 8 '13 at 23:15
1  
@SuzanneFrank Thank you! Please, add that to the statement of your question, rather than as just a comment; then, we can nominate the question for reopening. –  Nicholas R. Peterson Sep 8 '13 at 23:16

3 Answers 3

up vote 8 down vote accepted

Based on the OP's statement that she's trying to do this inductively:

You want to prove that for all $n$, the statement "$2^n3^{2n}-1$ is divisible by $17$" is true.

The first thing to do is to notice that $2^n3^{2n}-1=18^n-1$.

Next, you need to prove your base case: that is, that plugging in $n=1$, the result is true.

Last, you need to show that if the result holds for a given $n$, it also holds for $n+1$; that is, assuming that $18^n-1$ is divisible by $17$, prove that $18^{n+1}-1$ is also divisible by $17$.

By way of a hint for this last part, consider writing $18^{n+1}=18\cdot 18^n=18^n+17\cdot 18^n$. Can you see any way to make use of this?

share|improve this answer

$$2^n\cdot3^{2n}-1 = 18^n-1 = (18-1)(\cdots) = 17(\cdots)$$

share|improve this answer
5  
Alternatively, $18^n-1 \equiv 1^n-1 \pmod {17}$. –  Rebecca J. Stones Sep 8 '13 at 23:07
1  
@Rebecca, maybe add that as an answer - I'll upvote! –  davin Sep 8 '13 at 23:09
    
How did you take out $(18-1)$ as common? I see it as $18^n-18^0$, so, $18^0$ is common. –  Ramit Sep 9 '13 at 8:56
2  
@Ramit, $18^n-1=18^n-1^n$, en.wikipedia.org/wiki/… –  davin Sep 9 '13 at 10:42
    
that's interesting, thanks! –  Ramit Sep 9 '13 at 10:44

Hint: $2\cdot3^2=18$ and $18\equiv1\pmod{17}$

If you do not know that $$ a\equiv b\pmod{p}\implies a^n=b^n\pmod{p}\tag{1} $$ then $(1)$ can be proven by induction pretty easily.

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.