Minimum index Array Product
Here's a simple $O(n \log n)$ solution if multiplication and the modulus operator is always assumed to be $O(1)$ (which is a big assumption -- see the note at the end).

Create a new array, $B$, in which the first element is $A[1]$ and every future element at index $i \in 2..n$ is $A[i] * B[i-1]$. This gives you an array of all "partial products".

This array is nondecreasing, and $B[j]$'s factors are a superset or $B[i]$'s factors whenever $i &lt; j$. Therefore, for any $A[i]$ (or even for every integer $k$), you can use binary search to find the smallest index $i$ for which $k$ divides $A[1] * A[2] ... * A[i]$. This takes $O(\log n)$ time per lookup, or $O(n \ log n)$ in total for all of $A$.

--

Regarding the initial assumption. As it turns out, assuming arithmetic operations can be done in constant time gives you a bit more power than what most people consider reasonable. For example, one can factor arbitrary integers in polynomial time under this assumption, by constructing pathologically large multiplications/divisions that let them "carpool" many different operations into one. Do you know which cost model we are operating under?