Checking Divisibility Using Minimal Bits

Question

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.

Answer 1

For part (a), the idea is that it suffices to store the sum of all integers seen so far modulo $N$. Since this is an integer between $0$ and $N-1$, storing it requires only $\lceil \log_2 N \rceil$ bits.

For part (b), let $x_i = p_1^{a_1(i)} \cdots p_r^{a_r(i)} q$, where $q$ is relatively prime to $p_1,\ldots,p_r$. Then $x_1 \cdots x_m$ is divisible by $N$ iff $a_j(1) + \cdots + a_j(m)\geq k_j$ for $j=1,\ldots,r$. Hence it suffices to store $\min(a_j(1)+\cdots+a_j(m),k_j)$ for $j=1,\ldots,r$. The $j$th number is between $0$ to $k_j+1$, and so requires $\lceil \log_2 (k_j+1) \rceil$ bits, for a total of $$ \sum_{j=1}^r \lceil \log_2(k_j+1) \rceil \text{ bits}. $$ (In fact, we can be a little bit smarter and use only $\left\lceil \sum_{j=1}^r \log_2(k_j+1)\right\rceil$ bits, but it's not such a big difference.)

In both cases, it is possible to show that the amount of bits stated is also required. For example, in part (a), at any given point in time you need to distinguish between $N$ different states, correspond to the current sum modulo $N$. Indeed, all sequences $0;1;\cdots;N-1$ must lead to different memory states, since if $i$ and $j$ led to the same state, then we would not be able to distinguish between the sequences $i,N-i$ and $j,N-i$, although one of them satisfies the divisibility property and the other doesn't.