# For positive triplet (n,x,y), n/(x*y)==n/x/y even in integer division

More than 1 year has passed since last update.

For positive triplet (n,x,y), `n/(x*y)==n/x/y` even in integer division.

This should be useful to avoid overflow.

Let's prove this below.

if n.divmod(xy) is (a,b), n can be represented as:

```n=axy+b (0<=b<xy)
```

On the other hand, if n.divmod(x) is (c,d) and c.divmod(y) is (e,f), n can be represented as:

```n=cx+d (0<=d<x)
c=ey+f (0<=f<y)
n=x(ey+f)+d=exy+xf+d
```

Now suppose d is x-1 and f is y-1. Then `xf+d` becomes `x(y-1)+x-1=xy-1 (<xy)`.

This means `0<=xf+d<xy` and `a(==n/(x*y))==e(==n/x/y)` has been proved.

Also, in `n/(x*y)`, x and y are exchangable. So `n/x/y == n/y/x`. (Q.E.D.)

## 170513

Actually this lemma is used for icbrt (integer cubic-root) used in http://qiita.com/cielavenir/items/2a685d3080862f2c2c47 .

## 180127

For fear, I confirmed small case...

```#!/usr/bin/ruby
(1..10000).each{|n|
(1..100).each{|x|
(1..100).each{|y|
r0=n/(x*y)
r1=n/x/y
r2=n/y/x
if r0!=r1 || r1!=r2
raise [n,x,y].join(',')
end
}
}
}
```

https://qiita.com/cielavenir/items/d419b448d1c65eae2868 is another example where this lemma is useful.