# How do I calculate (((i * j) modulo 2^64) / k) modulo 2^64 and get the same result as ( (i * j) / k ) modulo 2^64?

Rest assured, it makes sense in context. Assume positive values only.

How do I calculate (((i * j) modulo 2^64) / k) modulo 2^64 and get the same result as ( (i * j) / k ) modulo 2^64?

-
Please reveal the context this makes sense in. Do you mean you want conditions on $i$, $j$, and $k$ that will guarantee this? $k=\pm 1$ or $ij < 2^{64}$ ought to do it. – Henning Makholm Oct 13 '12 at 20:37
They are congruent mod $2^{64}$. So it suffices to normalize them, i.e. pick some canonical system of residue representatives (e.g. least positive residues), then normalize the result so that it lies in that range. – Bill Dubuque Oct 13 '12 at 20:42
Sorry; I need to decompose the first equation into a series of equations which, when a set of i, j and k numbers are run through them, give the same final result as the second equation. – Narf the Mouse Oct 13 '12 at 20:50
What do you mean by "decomposing" an expression into another when there are values where the two expression give different results? – Henning Makholm Oct 13 '12 at 20:58

Note that $ij=u+k2^{64}$ where $0<=u<2^{64}$ You want to divide $ij$ or $u$ by $k$ mod $2^{64}$ so choose some $k'$ inverse to $k$, i.e. $kk'=1$ mod $2^{64}$.
Now it seems you want the calculation $uk'$ to give the same result as $ijk'$ mod $2^{64}$. This will of course happen automatically, in that the same results mod $2^{64}$ will occur for each. But if it happens that $k>0$ the two numbers, $uk'$ and $ijk'$, will be different, obviously. I think you can't do what you want, without having some kind of access to the value of $k$ (the number of times $2^{64}$ has to be added to $u$ to obtain $ij$).
Put simply: you can't just use the numbers $i,j,k$ and some chosen constants mod $2^{64}$ to do what you want. You'll need to use also an intermediate variable computed from the two numbers $i,j$. So you won't have a formula, just a procedure.