Let's consider the language over $\{0,1\}$ containing such words $w$ that: $$w = m_1m_2..m_n $$ where $m_i$ has length $n$. (so $|w|=n^2$) and $$m_1 + m_2 + .. + m_n \mod 3 = 0$$

($m_i$ we interepret as binary enoded number).

Prove, that the language is $NC^1$ class.

The first problem is: How to decide whether $m_i$ is divisable by $3$?

$m_i = a_na_{n-1}...a_0$ where $a_i$ is a bit, so the number interpreted is: $v = a_0 \cdot 2^0 + a_1 \cdot 2 + .. + a_n \cdot 2^n$.

My only observation is:

$$2^{2k+1} \mod 3 = 1 \\ 2^{2k} \mod 3 = 2$$

Please hint me.

Let's consider the language over $\{0,1\}$ containing such words $w$ that: $$w = m_1m_2..m_n $$ where $m_i$ has length $n$. (so $|w|=n^2$) and $$m_1 + m_2 + .. + m_n \mod 3 = 0$$

($m_i$ we interpret as binary encoded number).

Prove, that the language is $NC^1$ class.

The first problem is: How to decide whether $m_i$ is divisible by $3$?

$m_i = a_na_{n-1}...a_0$ where $a_i$ is a bit, so the number interpreted is: $v = a_0 \cdot 2^0 + a_1 \cdot 2 + .. + a_n \cdot 2^n$.

My only observation is:

$$2^{2k+1} \mod 3 = 1 \\ 2^{2k} \mod 3 = 2$$

Please hint me.