# Proof by Induction Help: Prove that there are unique integers $a\geq 0$ and $k>0$ such that $n=(3^a)\cdot k$ and $k$ is not divisible by $3$.

Suppose $n$ is a positive integer. Using induction, prove that there are unique integers $a\geq 0$ and $k>0$ such that $n=(3^a)\cdot k$ and $k$ is not divisible by $3$.

Note: I have already proven the base step of $P(1)$ and have set the induction hypothesis (I.H.) to be $P(t): t=(3^a)\cdot k$ [I used $t$ here instead of $k$ since $k$ already exists in the equation]. I am to the point of proving $P(t+1)$ but am unsure of whether or not this means $t+1=(3^a)\cdot k$ or if it means $t+1=(3^a)\cdot k+1$? With the latter, couldn't you just subtract a $1$ and then be left with your I.H.? If it is the first equation, I'm not quite sure how this can be proved. The induction proofs I have done so far were all summation problems, so I could group sections together and set it equal to the I.H. which doesn't seem to be a possibility here.

• Are you sure the condition is $a \geq 0$ and not $a > 0$? With $a$ allowed to be $0$, the question doesn't even require an inductive proof, since $\forall t$ which are not divisible by 3, we have $t = (3^0) \cdot t$, and for those which are divisible by 3 you can use prime factorization to remove the 3s and then plug all the rest into $k$. Are you required to use induction here?
– MM8
Jan 31 '17 at 1:09
• I just re-checked the homework sheet, it is in fact $a\geq 0$. Jan 31 '17 at 1:11
• Like I said, the result then follows immediately from prime factorization. Why do you want to frame such a proof in an induction? It's not impossible but certainly kind of artificial to do so.
– MM8
Jan 31 '17 at 1:21
• In class today the professor just stated that he suggest we prove the statement by some form of induction. I guess he did not say it was required, but I was curious how this would be done. Jan 31 '17 at 1:24
• @TimonG. Results like this are usually proved before those much stronger results. Jan 31 '17 at 1:24

Hint $\$ If $\,3\nmid n\,$ then $\, n = 3^{\large 0} n.\,$ Else $\,3\mid n\,$ so by induction $\,n/3\, =\, 3^{\large a}k,\ 3\nmid k,\,$ so $\,n = 3^{\large a+1}k.$
• If we are assuming $P(n)$ to be true, wouldn't the resulting cases be $3\nmid n+1$ and $3\mid n+1$? Jan 31 '17 at 1:38
• @Deno1133 We used strong/complete induction, did you not yet learn that form of induction? Our induction hypothesis is that it is true for all $\,k< n,\,$ so, in particular, for $\,k = n/3.\ \$ Jan 31 '17 at 1:40