Number theory problem in induction Without using the fundamental theorem of algebra (i.e. the prime factorization
theorem), show directly that every positive integer is uniquely representable as the product
of a non-negative power of two (possibly $2^0=1$) and an odd integer.
 A: Use strong induction.
The base cases are clear. Next suppose $n>1$ is an integer and that the result is true for all positive integers less than $n$.
Case $1$: $n$ is even. Then $\frac{n}{2}$ is an integer less than $n$ and so is expressible as $\frac{n}{2} = 2^k m$ for a unique odd $m$. Then $n = 2^{k+1} m$ is unique way to express $n$ in such a way.
Case $2$: $n$ is odd. Then $n = 2^0 n$ is one way to express $n$ in the required form. Suppose $n = 2^0 m$ for some other odd $m$, then clearly $m=n$ so the expression above is unique.
A: Existence: Every time we take a positive integer and divide it by $2$, it gets smaller.  So by the Well-Ordering Principle (equivalently, by the nonexistence of positive integers $n_1 > n_2 > ... n_k > ...$), eventually this process has to stop: thus we've written $x = 2^a y$ with $y$ not divisible by $2$ (which I assume is your definition of "odd".  It's a short argument involving the Division Theorem to show that an integer is odd if and only if it's of the form $2k+1$.) 
Uniqueness:  Suppose $x = 2^{a_1} y = 2^{a_2} z$ with $0 \leq a_1 \leq a_2$ and $y,z \in R$ and $y$ and $z$ not divisible by $2$.  Then $y = 2^{a_2-a_1} z$.  Since $y$ is not divisible by $2$ we must have $a_2 - a_1 = 0$, i.e., $a_1 = a_2$; since $\mathbb{Z}$ is an integral domain -- i.e., $AB = AC$ and $A \neq 0$ implies $B = C$ -- we conclude $y = z$.  
I claim that essentially the same reasoning proves a much more general result.

Proposition: Let $R$ be an integral domain satisfying the ascending chain condition on principal ideals (ACCP) -- e.g. a Noetherian domain -- and let $p$ be a nonzero, nonunit element of $R$.  Then every nonzero element $x \in R$ can be written as $p^a y$ with $p \nmid y$, and if $p^{a_1} y_1 = p^{a_2} y_2$, then $a_1 = a_2$ and $y_1 = y_2$.

Indeed, the uniqueness part of the argument holds verbatim with $2$ replaced by $p$.
Existence: If $x$ is not divisible by $p$, then we may take $a_1 = 0$ and $y =x$.  Otherwise, we may write $x = p y_1$.  If $y_1$ is not divisible by $p$, then again we're done; if not, we can write $y_1 = p y_2$, so $x = p^2 y_2$.  If at some point we reach $x = p^a y_a$ with $y_a$ not divisible by $p$, then we're done.  If not then $(y_1) \subsetneq (y_2) \subsetneq \ldots$ is an infinite strictly ascending chain of principal ideals, contradiction.  
Thus we've associated a sort of $\operatorname{ord}_p$ function to any nonzero nonunit in any domain satisfying ACCP.  This function is a discrete valuation if and only if $p$ is a prime element.  
