# How to compute (x MOD y) with just SUM and MULT gates?

It is known that $\{ SUM, MULT \}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates.

By the way, I could not come up with designing $MOD$ function with $SUM$- and $MULT$-only circuit. How can one construct such a circuit?

P.S. The Turing machine is simple. Assuming $\#x\#y\#$ as the input, it suffices to go back and forth and cross $y$ of the remaining entries of $x$ as much as possible.

If we have a sequence of circuits, one for each possible length of input, we can interpret the sequence as computing a function. As mentioned above, one way of generating such a sequence of circuits is from a Turing machine. Circuits which can be generated by a Turing machine, which accepts $n$ as input and outputs the circuit handling inputs of length $n$, are known as uniform circuits. (There are various more refined notions of uniformity, in which the Turing machine has some resource restrictions.) However, not all sequences of circuits arise in this way. For example, if $L$ is any length in which membership depends only on the length of the input, then $L$ can be computed by a sequence of circuits. However, $L$ need not even be computable. For example, consider the language of all inputs of length $n$ such that the $n$th Turing machine halts on the empty input.
You say that $\{SUM,MULT\}$ is Turing-complete, but there are a few problems with this statement. First, you seem to think of SUM and MULT as gates, which are components of circuits. As explained above, a model for circuits can't really be Turing-complete, though a set of gates can be complete in the sense that using it you can compute any function. Second, we usually (but not always) think of circuits as Boolean-valued. You haven't explained what the domain of SUM and MULT is, but I suspect that it is not $\{0,1\}$. In that case you have to explain exactly what circuit model you are interested in, and what notion of completeness you are interested in: while Boolean circuits can compute all functions $\{0,1\}^n \to \{0,1\}$, the same doesn't necessarily hold in other circuit models such as algebraic circuits.