In this paper, the author writes:

Now $k\phi(N) = ed - 1 < ed$. Since $e < \phi(N)$, we see that $k <d < \frac{1}{3}N^{\frac{1}{4}}$. Hence, we obtain:

$\mid \frac{e}{N} - \frac{k}{d} \mid \leq \frac{1}{dN^{\frac{1}{4}}} < \frac{1}{2d^2}$

I am having trouble seeing how these last equalities were found. I see how to get the following:
$\mid \frac{e}{N} - \frac{k}{d} \mid$ = $\frac{k}{d} - \frac{e}{N}$ $< \frac{3d}{dn^{\frac{1}{2}}} $

I do not see how to get from here to $\frac{1}{2d^2}$. Is anyone willing to explain this to me?


1 Answer 1


The previous part of the proof in that paper already shows that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{3k}{d\sqrt{N}}$. As $k < d$ we estimate this by $\frac{3d}{d\sqrt{N}}$, where the $d$'s cancel to get $\frac{3}{\sqrt{N}} = \frac{3}{N^{1 \over 2}} = \frac{3}{N^{1 \over 4}}\frac{3}{N^{1 \over 4}}\frac{1}{3}$.

As $d < \frac{1}{3}N^{\frac{1}{4}}$ we also get that $\frac{1}{d} > \frac{1}{\frac{1}{3}N^{{1 \over 4}}} = \frac{3}{N^{{1 \over 4}}}$.

Combining we get that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{1}{3d^2}$, which is even a better bound (the 2 might be the constant in the continued fraction convergents theorem, so that might explain it presence).

  • $\begingroup$ Thanks, I wasn't seeing the inequality, but its very clean now $\endgroup$
    – 1west
    Commented Dec 3, 2015 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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