Given $n$ integers, $x_1, ... , x_n$, is there some well-known procedure or algorithm that checks if the product $x_1 * ... * x_n$ is divisible by some arbitrary prime $N$ using minimal space?
Since the product and $N$ can be arbitrarily large, I don't think you can just simply use modular arithmetic to see if the remainder is $0$. I was thinking maybe convert the product to its prime factorization, and if $N$ isn't one of the primes used, then we know the product cannot be divisible by $N$, right? Does this seem like something that could work?
Note that primes are prime: that is, if $p \mid a b$ then $p \mid a$ or $p \mid b$. (This is Euclid's lemma.) Inductively, then, if $p \mid x_1 x_2 \dots x_n$ then $p$ divides some $x_i$. So just check each of the $x_i$ in turn. Modular arithmetic is fine for that.