Lets say we have $n$, an odd semiprime. $p$ and $q$ are odd primes, such that $pq=n$. What are the tightest upper and lower bounds of $p+q$ in terms of $n$ known right now? Right now, I have $2\sqrt n\leq p+q<n$ but I don't know if that's the tightest possible.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ upper would be when $p=3$ and lower would be when $p=\sqrt n$ $\endgroup$– J. W. TannerCommented Jun 16, 2019 at 20:43
-
$\begingroup$ No, I meant what is the range of values $p+q$ can fall into. $\endgroup$– DUO LabsCommented Jun 16, 2019 at 20:45
-
$\begingroup$ Note: $p+q=p+n/p$ $\endgroup$– J. W. TannerCommented Jun 16, 2019 at 20:46
-
$\begingroup$ Yes, but how is that any helpful? $\endgroup$– DUO LabsCommented Jun 16, 2019 at 20:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Summing up the comments; without loss of generality $3\leq p\leq\sqrt{n}\leq q$, and because $n=pq$ we have $$p+q=p+\tfrac np,$$ which is maximal when $p$ is minimal, and minimal when $p$ is maximal. Hence $$2\sqrt{n}\leq p+q\leq 3+\tfrac n3.$$
-
-
$\begingroup$ In what sense? For each semiprime $n$ the value of $p+q$ is uniquely determined, but my answer gives a range of values. For $n=9$ both inequalities are tight, though. $\endgroup$– ServaesCommented Jun 16, 2019 at 21:27
-
-
$\begingroup$ Because $p$ is an odd prime, so $p\geq3$. $\endgroup$– ServaesCommented Jun 17, 2019 at 11:26
-