Suppose we're given an infinite stream of integers, $x_1, x_2, \dots$.
a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log N)$ bits of memory.
b) Let $N$ be an arbitrary number, and suppose we're given $N$'s prime factorization: $N = p_1 ^{k_1} p_2 ^{k_2} \dots p_r ^{k_r}$. How would you check whether $N$ divides the product of all integers $x_i$ seen so far, using as few bits of memory as possible? Write down the number of bits used in terms of $k_1, ..., k_r$.
For part a), we know that for any prime $p \ne 2, 5$, there is an integer $r$ such that in order to see if $p$ divides a decimal number $n$, we break $n$ into $r$-tuples of decimal digits, add up these $r$-tuples, and check if the sum is divisible by $p$. But $N$ is a fixed integer, and not necessarily a prime. Is there some way to connect the theorem above to any arbitrary integer?
For part b), for the product of $x_i$ (call it $y$) is divisible by $N$, then $y$ must be divisible by each $p_i ^{k_i}$ (call it $a_i$. Since we're given the prime factorization, we can just check if $y$ is divisible by $N$ by dividing $y$ by each $a_i$ and halting when it fails, right? Would this result in using $k_1 \times \dots \times k_r$ bits?
Am I at least on the right track, or am I completely wrong? Any help understanding this problem would be tremendously helpful.