# For what c is division by c in AC0?

Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer. This is just a shift if $c$ is a power of two, but what about other numbers? Can we do it with a constant depth circuit for every $c$? What about $c=3$?

ps. I know that computing $x\bmod c$ is hard, but this seems unrelated.

For any constant number $c$, $x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$): $$x \bmod c = x - (\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}})$$
It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$ which is not a power of $2$. Thus $\lfloor x/c \rfloor$ is hard for $\mathsf{AC^0}$ for any $c$ which is not a power of $2$.
As noted by Emil in the comments there is an easy reduction for odd prime $c$ from $\mathit{MOD}_c$ (that is, $\sum_ix_i\bmod c$ with $x_i\in\{0,1\}$) to $x\bmod c$ with binary input: we use only input bits which are multiples of $p-1$ and use FLT ($2^{(p-1)i} \bmod p = 1$).
• The same argument applies to any $c$ which is not a power of 2. Commented Dec 2, 2014 at 23:33
• That $x\bmod c$ is not AC^0 for other $c$ is easy to show: for instance, we can assume $c=p$ is an odd prime, and then you can reduce MOD_p to it by using every $(p-1)$th bit. Or you can apply the Barrington-Thérien classification: it's a regular language, and its syntactic monoid is a nontrivial group. Commented Dec 2, 2014 at 23:42