# Modulo of (Power of 2 divided by a number)

I wanted to calculate the power of $2$ raised to a number $a$, divided by another number $b$ and then take the modulo $K$ of this quantity.

Meaning, I basically wanted $(2^a/b) \mod K$. Take an example where $a = 4$, $b = 3$ and $K = 98765431$. For this I calculated $3^{-1} \mod K$. Which comes out to be 65843621 *. If this inverse is correct and I now do $(2^4 \cdot 65843621) \mod K$, the answer comes out to be incorrect. I don't know what the problem with my approach is.

*The way I calculated inverse is the following. $3 \cdot x = 98765431 \cdot n + 1$, so I iterated over $n$ to see when $98765431 \cdot n + 1$ is divisible by $3$ and then $x$ is my desired inverse.

-
What is your result? What do you compare your "incorrect" result to? Where does this number come from? – Simon Markett Aug 31 '12 at 11:13
I got the same inverse for three that you did. That gives $$2^4\cdot 3^{-1}\equiv 65843626\pmod{K}$$ as the result. Did you get the same? If yes, why do think this would not be correct? You can also calculate this as $$\frac{16}3=5+\frac13\equiv 5+65843621=65843626\pmod{K}.$$ – Jyrki Lahtonen Aug 31 '12 at 11:13
Ok, at the risk of sounding stupid, $2^4 = 16$ and $16/3 = 5$ so I should be getting $5%K = 5$, since $5 < K$. And I did get $65843626$ as the result too. – n0nChun Aug 31 '12 at 11:17
$\frac {16}{3}=5+3^{-1}$ and $3^{-1}=65843621$ – Simon Markett Aug 31 '12 at 11:19
Floor doesn't mix with modular arithmetic. Sorry. Integer arithmetic is always precise. – Jyrki Lahtonen Aug 31 '12 at 11:20

## 1 Answer

Ok. Comments revealed the source of the confusion. As a general philosophy here I want to mention the following. In the ring $R=\mathbb{Z}_K$ the residue class of $3$ has an inverse, namely the residue class of $65843621$. What this means is that we are replacing "division by $3$" with "multiplication by $65843621$". The result of such a multiplication is another integer (or a residue class modulo $K$ to be precise). What this means is that the result is "accurate". There is no rounding error.

Another way of saying the same thing is that because $3$ is a unit in the ring $R$, every other element of the ring is exactly divisible by $3$.

Another thing that newcomers to modular arithmetic often have problems with is the following. In a ring like $R$ here there is no meaningful$^{*)}$ concept of a size of an element, nor a meaningful way of saying that one element is larger than another. For example, if we assume that $0<1$, then we probably want to accept as a consequence that $1=0+1<1+1=2$, and as another consequence that $0<1<2$, so $0<2$. Continuing in this way we would have to accept as a consequence that $0<K-1$. But here $K-1\equiv -1$, so we end up with $0<-1$. This renders the order relation useless.

The floor function ultimately depends on a sense of "betweenness" (a real number between two consequtive integers), so it, too, becomes meaningless in rings of modular integers.

$^{*)}$ Ok, some meaningful metrics can sometimes be defined, but they follow somewhat different rules than the familiar absolute value.

The problem that OP linked to is about the following. Let $J$ be the all ones $n\times n$ matrix, and let $I$ be the identity matrix with $n$ rows. A calculation by $n$ "cows" is to be carried out $T$ times. A single round of the calculation amounts to multiplying a certain vector with $n$ components, all from the ring $R$, with the matrix $-I+J$ (obviously modulo $K$). Altogether the task at hand is to efficiently compute the matrix power $$A_T=(-I+J)^T,$$ where $T$ is a large integer.

Here we have the "atomic" rules $I\cdot I$, $I\cdot J=J$ and $J\cdot J=nJ$. As always, when computing large powers in a ring of modular integers, the so called square-and-multiply method works. As a consequence of the above rules we get the formula $$(aI+bJ)(cI+dJ)=acI+(ad+bc+bdn)J,$$ all the coefficients are to be reduced modulo $K$. That's all we need! By induction we see that for all natural numbers $k$ $$A_k=f(k)I+g(k)J,$$ and the task at hand is to compute the integers $f(T)$ and $g(T)$. All you need to do is to first compute $A_2$, $A_4$, $A_8$, $\ldots$ by repeated squaring $\log_2(T)$ squarings. Then you need to multiply the appropriate ones together using the above rule. Shouldn't take too long. Edit: Observe that you only need to compute and store the integers $f(k)=(-1)^k$ and $g(k)$ for the relevant integers $k$.

-
Thanks kind sir :) – n0nChun Aug 31 '12 at 11:40
@nonChun: I added my take of the cow problem. Didn't double check anything, but it seems to me that this is what is required. – Jyrki Lahtonen Aug 31 '12 at 11:53
I understand this method, and I wanted to use it too, but if n is large say 50000, then the matrix sizes $O(n^2)$ become huge! – n0nChun Aug 31 '12 at 12:28
@nonChun: If I understood correctly, you don't have to store the matrices. Only the numbers $f(k)$ and $g(k)$. You only need the "full" matrix at the end, when computing the cows total output. Also, it seems to me that $f(k)=(-1)^k$, so there is only $g(k)$ to worry about. – Jyrki Lahtonen Aug 31 '12 at 12:34
Hey jyrki, I was able to reduce the problem of finding the coefficients of I and J to finding the exponentiation of a 2x2 matrix and my solution got accepted! Thanks for the pointers :) btw, why did you think of breaking the problem into I - J , and not the original matrix? – n0nChun Sep 1 '12 at 11:09