What's the most efficient algorithm for Divisibility?
Fleshing out my comments into an answer: since divisibility is (trivially) reducible to division, and since division is (nontrivially) reducible to multiplication via approaches like Newton's method, then your problem should have the same time complexity as integer multiplication.  AFAIK, there are no known lower bounds for multiplication better than the trivial linear one, so the same should hold true of your problem - and in particular, since multiplication is known to have (essentially) $O(n\log n\log^* n)$ algorithms, your hopes for a $n\log n\log\log n$ lower bound are almost certainly in vain.

The reason that division reduces precisely in complexity to multiplication &mdash; as I understand it &mdash; is that Newton's method will do a sequence of multiplications of different escalating sizes; this means that if there's an algorithm for multiplication with complexity $\Theta(f(n))$ then the complexity of a division algorithm using this multiplication algorithm as an intermediate step will be along the lines of $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ &mdash; and for all of the complexity classes under discussion this is just $\Theta(f(n))$.