How do you solve this recurrence relation with divides? I am trying to find all sequences $(a_n)$ of positive integers with the following property: for all $m$ and $n$, $a_ma_n$ divides $a_{m+n}$.  I’m not sure whether this counts as a recurrence relation or not, given the presence of “divides”.
Two sequences that satisfy it are $b^n$ for any positive integer $b$, and $n!$.  But how would I find the general solution?

For any prime $p$ and $k\in \mathbb N^+$, let $\nu_p(k)$ be the largest power of $p$ dividing $k$. The divisibility condition implies $\nu_p(a_{n+m})\ge \nu_p(a_n)+\nu_p(a_m)$, so that the sequence $\nu_p(a_n)$ is super-additive in $n$ for all $p$. Clearly, this is sufficient as well.
This gives a full characterization of all sequences $a_n$ which work; they are defined by a collection of super-additive sequences $\nu_p(a_n)$ for each prime $p$, with the only constraint between the sequences being that for each $n\in\mathbb N$, $\nu_p(a_n)$ must be nonzero for only finitely many $p$.
There are several infinite classes of examples here.
