State/Natural numbers can be factored into primes

• $1 < a < n$.
• $1 < b < n$.
• $ab = n$.

By the inductive hypothesis, it follows that both $a$ and $b$ have prime factorizations. Hence, there exist finite sequences $p_0, \ldots, p_{k-1}$, and $q_0, \ldots, q_{\ell-1}$ of prime numbers, such that: $$a = \prod_{i=0}^{k-1} p_i, \mbox{ and } b = \prod_{j=0}^{\ell-1} q_j.$$ Since $ab = n$, it follows that $n$ can be factored using the concatenation of the sequences $(p_i)$ and $(q_j)$. Namely, $$n = ab = \left( \prod_{i=0}^{k-1} p_i \right) \left( \prod_{j=0}^{\ell-1} q_j \right) = \prod_{t=0}^{j+k-1} r_t,$$ if $r = Conc(p, q)$.