7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Sep 8 '13 at 23:07
  • $\begingroup$ 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. $\endgroup$ Sep 8 '13 at 23:15
12
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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