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

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.

-
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
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

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?

-

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

-
Alternatively, $18^n-1 \equiv 1^n-1 \pmod {17}$. – Rebecca J. Stones Sep 8 '13 at 23:07
@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
@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.

-