# How to shift right in modular arithmetic $2^n$ using only subtraction and multiplication.

In modular arithmetic $$2^n$$ it is easy to shift left number $$x$$ by doing $$(x\ll 1)=2x=x+x=x-(0-x)$$. Shifting right on the other hand is integer division by the power of 2, e.g. $$(x\gg 1)=\lfloor x/2 \rfloor$$. My question: Is it possible to shift right using only addition, subtraction and multiplication? I suspect it is not possible.

I do not have direct access to the bits of the number. I know that the operation $$(x\ll (n-1)) \pmod{2^{n+1}}$$ effectively gives $$(x\gg 1)$$ in the upper half of the bit array. This trick is not good since it requires erasing the lower half, which is not addition/subtraction/multiplication.

By squaring the number a few times it is possible to calculate $$(x\&1)=x\%2=(x \pmod 2)$$, because all odd numbers give $$1$$ and all even give $$0$$. This is erasing all higher bits except the lowest. But erasing lower bits leaving the higher is also questionable.

• You should explain what a shift is since not everyone here has a programming background. – Toby Mak Dec 21 '18 at 5:55
• You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$ – gammatester Dec 21 '18 at 9:11
• Thanks, edited accordingly. – oddy Dec 22 '18 at 6:36

## 1 Answer

No, it's not possible for $$n\geq 2$$.

Suppose there is some polynomial $$p(X) \in (\mathbb{Z}/2^n \mathbb{Z}) [X]$$ such that $$p(a) = \lfloor \frac{a}{2}\rfloor$$ for all $$a\in \mathbb{Z}/2^n \mathbb{Z}$$.

First, set $$a=0$$. Since $$p(0) = 0$$, the constant term of $$p$$ is $$0$$.

Next, set $$a=2^{n-1}$$. Since $$(2^{n-1})^2 = 2^{2n-2}$$ and $$2n-2 \geq n$$, all the terms of $$p(2^{n-1})$$ are zero besides possibly the linear term. But $$p(2^{n-1}) = 2^{n-2}$$, while the linear term is divisible by $$2^{n-1}$$, contradiction.

• Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1. – Peter Taylor Dec 22 '18 at 8:08