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<e$. 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)$$