# How to elegantly find the remainder of $en$ divided by $n+1+\frac{n-1}{d}$

1. Motivation:

Let $$n,e,d$$ be positive integers greater than 2, such that $$e\mid n-1$$ and $$d\mid n-1$$. Denote $$N=en$$, $$M=n+1+\frac{n-1}{d}$$. Find $$q,r\in \mathbb{Z}$$ such that $$N=qM+r, 0\le r < M.$$

2. My trying:

Since $$N$$ and $$M$$ are intgeres, there uniquely exist such integers $$q,r$$ by division algorithm.

Obviously it has $$q. If $$q=e-1$$, then $$r=n+1-e-\frac{(e-1)(n-1)}{d}$$ under the condition that $$n\ge e-1+\frac{(e-1)(n-1)}{d}.$$ Furthermore, If $$q=e-k$$ with $$1\le k\le e-1$$, then $$r=k(n+1)-e-\frac{(n-1)(e-k)}{d}$$.

Next I try to require $$r$$ to satisfy $$0\le r < M=n+1+\frac{n-1}{d}$$. Then I get $$0\le kd(n+1)-ed-(n-1)(e-k)< d(n+1)+(n-1).$$

However, the inequality looks very complicatied.

3.Questions

Question:

How to elegantly find the remainder of $$N$$ divided by $$M$$ Or how to simplify the inequality? $$0\le kd(n+1)-ed-(n-1)(e-k)< d(n+1)+(n-1).$$

Thanks for any replies.

As you wrote, we have $$q=e-k\qquad\text{and}\qquad r=k\left(n+1+\frac{n-1}{d}\right)-e\left(1+\frac{n-1}{d}\right)$$ under the condition that $$0\le r\lt M,$$ i.e. $$0\le k\left(n+1+\frac{n-1}{d}\right)-e\left(1+\frac{n-1}{d}\right)\lt n+1+\frac{n-1}{d},$$ i.e. $$\frac{e(d+n-1)}{dn+d+n-1}\le k\lt \frac{e(d+n-1)}{dn+d+n-1}+1,$$ i.e. $$k=\left\lceil \frac{e(d+n-1)}{dn+d+n-1}\right\rceil$$

It follows that the answer is $$q=e-\left\lceil \frac{e(d+n-1)}{dn+d+n-1}\right\rceil$$ and $$r=\left\lceil \frac{e(d+n-1)}{dn+d+n-1}\right\rceil\left(n+1+\frac{n-1}{d}\right)-e\left(1+\frac{n-1}{d}\right)$$

• Wonderful! the ceiling function plays an important role. – zongxiang yi Mar 15 at 2:30