Can $a \bmod 3$ be represented arithmetically without the mod or other integer-related functions?

Question

I've noticed that $a \bmod b$ (with 'mod' in the operational sense) can also be represented using various tricks of formulation. For instance, that

$$a \bmod b = a - b\left\lfloor\frac{a}{b}\right\rfloor .$$

There are several ways to do it by (ab)using various functions like ceiling, max, abs, and the like. However, I realized yesterday that

$$a \bmod 2 = \frac{1-(-1)^a}{2}.$$

I find this interesting as I consider basic exponentiation to be a purer operation in some sense than something like floor, perhaps in that it doesn't have a built-in sense of conditionality or knowledge of fractional parts. Furthermore, you can use substitution to reach arbitrarily high powers of $2$, as in

$$a \bmod 4 = \frac{1-(-1)^a}{2}+1-(-1)^{\frac{a-\frac{1-(-1)^a}{2}}{2}},$$

which amounts to right-shifting $a$ by one spot and repeating the process to get the second bit you need for the $\bmod 4$. I realize that's not pretty, but I'm interested that it's possible. The motivation here is identifying situations where formulae may implicitly support a richness of computational complexity one wouldn't expect, which parity detection and manipulation goes a long way towards. Which leads me to my question:

Is there some way using exponentiation or other basic operations to find a comparable expression for $a \bmod 3$, or ideally, $a \bmod b$?

Answer 1

Any function $f(n)$ on the integers that is periodic with period $m$ can be written in terms of powers of $\zeta=e^{2\pi i/m}$, a primitive $m$th root of unity: $$ f(n) = \sum_{k=0}^{m-1} \hat f(k) \zeta^{nk}, \quad\text{where } \hat f(k) = \frac1m \sum_{j=0}^{m-1} f(j) \zeta^{-jk}. $$ Notice that when $m=2$, we have $\zeta=-1$ and this formula becomes $$ f(n) = \hat f(0) + \hat f(1)(-1)^n, \quad\text{where } \hat f(0) = \frac12(f(0)+f(1)) \text{ and } \hat f(1) = \frac12(f(0)-f(1)); $$ this is the formula you included when $f(n) = n\mod 2$.

When $m=3$, we have $\zeta=e^{2\pi i/3} = \frac12(-1+i\sqrt3)$ and $\zeta^2=\bar\zeta=\frac12(-1-i\sqrt3)$, and $$ f(n) = \hat f(0) + \hat f(1) \zeta^n + \hat f(2) \bar\zeta^n. $$ In the specific case $f(n)=n\mod 3$, the coefficients are \begin{align*} \hat f(0) &= \frac13(0+1+2) = 1, \\ \hat f(1) &= \frac13(0+1\bar\zeta+2\zeta) = -\frac12+\frac i{2\sqrt3}, \\ \hat f(2) &= \frac13(0+1\zeta+2\bar\zeta) = -\frac12-\frac i{2\sqrt3}. \end{align*} Putting it all together, $$ n\mod3 = 1 + \bigg({-}\frac12+\frac i{2\sqrt3}\bigg)\bigg(\frac{-1+i\sqrt3}2\bigg)^n + \bigg({-}\frac12-\frac i{2\sqrt3}\bigg)\bigg(\frac{-1-i\sqrt3}2\bigg)^n. $$

Answer 2

Note that $\sin(2\pi n/3)=0, \dfrac{\sqrt3}2, $ or $-\dfrac{\sqrt3}2$, according as $n\equiv0, 1, $ or $2\bmod3$, respectively.

Furthermore, $f(x)=\dfrac{x\left(x-\dfrac{\sqrt3}2\right)2}{-\dfrac{\sqrt3}2\left(\dfrac{\sqrt3}2-\dfrac{\sqrt3}2\right)}+\dfrac{x\left(x+\dfrac{\sqrt3}2\right)1}{\dfrac{\sqrt3}2\left(\dfrac{\sqrt3}2+\dfrac{\sqrt3}2\right)}=\dfrac{3x^2-\dfrac{\sqrt3}2x}{\dfrac 32}=2x^2-\dfrac x{\sqrt3}$

has the property that $f(0)=0, f\left(\dfrac{\sqrt3}2\right)=1, $ and $f\left(-\dfrac{\sqrt3}2\right)=2$.

Therefore, $f(\sin(2\pi n/3))=2\sin^2(2\pi n/3)-\dfrac {\sin(2\pi n/3)}{\sqrt3}=n \bmod 3.$