# Integral solutions to $a_1 \cdot a_2 \cdots a_k = N$

How many integral solutions are possible for the equation $a_1 \cdot a_2 \cdots a_k = N$ where each of $a_1,a_2,\ldots,a_k$ satisfy the property $0 ≤ a_i ≤ 9$?

• Look at the prime factorization of $N$. It should be of the form $2^{r_2}3^{r_3}5^{r_5}7^{r_7}$ (no solution exists if there are other prime factors). All $5$s and $7$s should be present among $a_i$ as themselves, so there are $\binom{k}{r_5} \binom{k-r_5}{r_7}$ ways to do it (again, solution doesn't exist if $k > r_5+r_7$). So, the problem now reduces to number of solutions of $a_1 a_2 \ldots a_r = 2^{r_2}3^{r_3}$, where $r=k - r_5 - r_7$. – polkjh Jan 10 '13 at 11:30

First, you need to factor $N$ as $N=p_1^{r_1}\cdot...\cdot p_k^{r_k}$ where $p_i$ are distinct primes. Observe that $a_1\cdot...\cdot a_n=N$ if and only if $a_i=p_1^{r^{(i)}_1}\cdot...\cdot p_k^{r^{(i)}_k}$ with $\sum_{i=1}^n r^{(i)}_j=r_j$. So your problem is equivalent to writing each $r_i$ as a sum of non-negative integers.
Clearly, your condition on $a_j$ makes it impossible for any $N>9n$ or any $N$ with primes bigger than $7$ in it's factorization.