Proof for a modular arithmetic identity.

Question

How can I prove the following? Or is there a reference to the proof for this?

$$d \mod abc = d \mod a + a\left(\left\lfloor\frac{d}{a}\right\rfloor \mod b\right)+ab\left(\left\lfloor\frac{d}{ab}\right\rfloor \mod c\right)$$

Answer 1

Let $d = r + ka; 0\le r < a$. Then $r =$ what you are referring to as $d\mod a$. And $k = [\frac da]$.

Let $k = s + mb; 0 \le s < b$ so $s = [\frac da] \mod b$ and $m =[\frac d{ab}]$

Let $m = t + nc; 0 \le t< c$ so $t = [\frac d{ab}] \mod c$

$d = r + ka=$

$r + (s+mb)a = r+(s+(t+nc)b)a = r + sa + tba + n*abc$

And $r + sa + tba \le (a-1) + (b-1)a+ (c-1)ba = a-1 + ab -a +abc - ba = abc - 1$.

So $r + sa + tba = d \mod abc$.

And $r + sa + tba = d\mod a + a([\frac da] \mod b) + ab([\frac d{ab}] \mod c)$.

====

We can try to do it more directly. By division algorithm:

for and $n,q$ there are unique integers $d,r$ so that $n = dq + r$ were $0 \le r < q$.

It's simple to see that $dq \le n < dq + q$ so $d \le \frac nq < d+1$ so $d = [\frac nq]$.

And this exercise, although it makes my teeth hurt to see it, seems to be taking $n \mod q$ to be and operation that is defined to be equal to $r$ as a definition. (So be it, I'm tired of arguing).

So $n = (n\mod q) + q*[\frac nq]$ is an identity. Furthermore if $n = a + q*[\frac nq]$ it follows that $a = (n\mod q)$.

Hence $d = (d \mod a) + a([\frac da])$

$= (d \mod a) + a([\frac da]\mod b + b([\frac {[\frac da]}b]))$

$=(d \mod a) + a([\frac da]\mod b + b([\frac {[\frac da]}b]\mod c + c([\frac{[\frac {[\frac da]}b]}c])))$

$= (d\mod a) + a([\frac da]\mod b) + ab([\frac {[\frac da]}b]\mod c) + abc*([\frac{[\frac {[\frac da]}b]}c])$.

So it only remains to show that $[\frac {[\frac da]}b] = [\frac a{ab}]$ and that $[\frac{[\frac {[\frac da]}b]}c] =[\frac a{abc}]$; something I glided over in my above proof.

Simple enough:

Lemma: $[\frac {[\frac mn]}k] = [\frac m{nk}]$ (for positive integers).

Proof: $[\frac mn] \le \frac mn < [\frac mn]+1$

$\frac{[\frac mn]}k \le \frac m{nk} < \frac{[\frac mn]}k + \frac 1k$

$[\frac{[\frac mn]}k] \le\frac{[\frac mn]}k \le \frac m{nk} < \frac{[\frac mn]}k + \frac 1k$

Meanwhile $[\frac{[\frac mn]}k]+ 1= [\frac{[\frac mn]}k]+ \frac kk > \frac{[\frac mn]}k$. And as $[\frac mn]$ is an integer. $[\frac{[\frac mn]}k]+ \frac {k-1}k \ge \frac{[\frac mn]}k$.

So $[\frac{[\frac mn]}k] \le \frac m{nk} < \frac{[\frac mn]}k + \frac 1k\le [\frac{[\frac mn]}k]+ \frac {k-1}k +\frac 1k = [\frac{[\frac mn]}k]+1$

So $[\frac m{nk}]=[\frac{[\frac mn]}k]$

So

$d= (d\mod a) + a([\frac da]\mod b) + ab([\frac {[\frac da]}b]\mod c) + abc*([\frac{[\frac {[\frac da]}b]}c])$

$= (d \mod a) +a([\frac da]\mod b) + ab([\frac {d}{ab}]\mod c)+ abc([\frac {d}{abc}])$.

And $d = (d\mod abc) + abc([\frac {d}{abc}])$.

So $d\mod abc = (d \mod a) +a([\frac da]\mod b) + ab([\frac {d}{ab}]\mod c)$

Answer 2

Numerical example: $$\begin{align}95 \mod \color{red}2\cdot \color{green}3\cdot \color{blue}7 = \color{purple}{\mathbf{11}} \Rightarrow \frac{95}{\color{red}2\cdot \color{green}3\cdot \color{blue}7}&=\frac{(1+94)}{\color{red}2\cdot 3\cdot 7}=\\ &=\frac{1}{2\cdot 3\cdot 7}+\frac{2\cdot 47}{2\cdot 3\cdot 7}\\ &=\frac{1}{2\cdot 3\cdot 7}+\frac{2\cdot (2+45)}{2\cdot \color{green}3\cdot 7}=\\ &=\frac{1}{2\cdot 3\cdot 7}+\frac{2\cdot 2}{2\cdot 3\cdot 7}+\frac{2\cdot 3\cdot 15}{2\cdot 3\cdot 7}=\\ &=\frac{1}{2\cdot 3\cdot 7}+\frac{2\cdot 2}{2\cdot 3\cdot 7}+\frac{2\cdot 3\cdot (1+14)}{2\cdot 3\cdot \color{blue}7}=\\ &=\frac{1}{2\cdot 3\cdot 7}+\frac{\color{red}2\cdot 2}{2\cdot 3\cdot 7}+\frac{\color{red}2\cdot \color{green}3\cdot 1}{2\cdot 3\cdot 7}+2=\\ &=\frac{\color{purple}{\mathbf{11}}}{\color{red}2\cdot \color{green}3\cdot \color{blue}7}+2.\end{align}$$