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

Mathematics Asked on January 5, 2022

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 – bleftlfloorfrac{a}{b}rightrfloor .$$

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$$?

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

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

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

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

Answered by J. W. Tanner on January 5, 2022

Any function $$f(n)$$ on the integers that is periodic with period $$m$$ can be written in terms of powers of $$zeta=e^{2pi i/m}$$, a primitive $$m$$th root of unity: $$f(n) = sum_{k=0}^{m-1} hat f(k) zeta^{nk}, quadtext{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, quadtext{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) = nmod 2$$.

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

Answered by Greg Martin on January 5, 2022

Related Questions

Is cardinality of sigma-algebra for two independent random variables is the sum of cardinalities of two sigma-algebras?

0  Asked on January 11, 2021

expectation of random probability measure

1  Asked on January 11, 2021 by xiao

How many solutions are there to $x_1 + x_2 + x_3 + x_4 = 30$ s.t. $x_1 + x_2 le 20$ and $x_3 ge 7$?

1  Asked on January 11, 2021 by lucas-peres

How to prove that this series of functions is uniformly convergent?

1  Asked on January 10, 2021 by applesauce44

Proving that holomorphic map $f : mathbb{C}^n to mathbb{C}^m$ maps holomorphic tangent space at point $p$ to holomorphic tangent space at $f(p)$

0  Asked on January 10, 2021 by emptyvessel

Let $X$ be a metric space without isolated points. Then the closure of a discrete set in $X$ is nowhere dense in $X$.

3  Asked on January 10, 2021 by turingtester69

Fundamental theorem of Riemannian Geometry question

2  Asked on January 10, 2021 by monoidaltransform

If given two groups $G_1,G_2$ of order $m$ and $n$ respectively then the direct product $G_{1}times G_{2}$ has a subgroup of order $m$.

2  Asked on January 10, 2021 by user3133165

Show that if ${s_{n_k}}_k$ converges to $L$, then ${s_n}_n$ converges to $L$.

0  Asked on January 10, 2021 by xhsbm

Understanding roots of complicated equations

3  Asked on January 9, 2021 by landon-carter

How many solutions does the equation have? (Inclusion-exclusion principle)

1  Asked on January 9, 2021 by socket1814

Find the eigenspaces corresponding respectively to each eigenvector

0  Asked on January 9, 2021 by jojo

Order of a Module

0  Asked on January 9, 2021 by user193319

Intuition behind the extected value formula, for continuous cases

1  Asked on January 9, 2021 by thenac

Proof that the set $mathbb{Q}left[sqrt2right]$ is an $mathbb{Q}$-vector space

3  Asked on January 9, 2021 by robertoherb

How can we find A using finite difference method?

1  Asked on January 8, 2021 by momo

Probability question about picking $2$ types of balls out of $3$

2  Asked on January 8, 2021 by ryan-soh

Let $def*#1{mathbf{#1}}*{u},*{v},*{w}inmathbb{R}^2$ be noncollinear. Show that $*{x}= r*{u}+s*{v}+t*{w}$ where $r+s+t=1$.

2  Asked on January 8, 2021

Retract of $F_2$ onto $[F_2,F_2]$

2  Asked on January 8, 2021 by sasha

Terence Tao Analysis I on defining subtraction operation problem

1  Asked on January 8, 2021