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.



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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.