Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory doubt

  1. Dec 20, 2011 #1
    Given a number pq that is the product of two positive integers p and q, is there any way of finding with good precision, (p-1)(q-1)? Or any approximation at the least?

    Thanks in advance! :D
  2. jcsd
  3. Dec 20, 2011 #2
    I assume that p and q are prime.
    The answer is almost certainly no, given that prime factorization is a very difficult problem and that being able to compute (p-1)(q-1) would give you a great deal of information about p an q.
  4. Dec 20, 2011 #3
    But you see, for large values of p & q, (p-1)(q-1) is approximately 0.9999....times pq. I was just hoping maybe this approximation could be pinpointed.

    What if p and q aren't prime?Is it possible to obtain anything?
  5. Dec 20, 2011 #4
    Even if p and q aren't primes you would still get .999...times pq for high values of p and q.
  6. Dec 20, 2011 #5
    This is probably a way you could think of it. If you look at it as a limit as p and q approach inf. what would you get?
  7. Dec 20, 2011 #6


    User Avatar
    Science Advisor
    Homework Helper

    On the other hand if p = 2, (p-1)(q-1) is approximately 0.5 times pq.

    I don't see this is going anywhere, unless you rethink what your question really is.
  8. Dec 20, 2011 #7
    Maybe some rough approximation could be done. Ignore for the moment the primality of p or q, to concentrate only on their magnitudes. As (p-1)(q-1) = pq - (p + q - 1), you can have an idea of the difference (p + q - 1) depending on how far the factors differ from sqrt(pq).

    Here is a graph of (p + q - 1) for pq = one million, for p varying from 100 to 1000, where you see how the curve flattens to the right.

    http://img684.imageshack.us/img684/6084/pq1.png [Broken]

    When p = q = sqrt(pq) (as in the value 1000 on the X-axis of the graph), the difference (p + q - 1) becomes 2 sqrt(pq) - 1 (1999, in our example); when the smaller factor is half the geometric mean, or sqrt(pq) / 2 (as when the value in the X-axis is 500), the difference is (5/2) sqrt(pq) - 1 (2499 in this example).

    So, if the smaller factor does not go farther than half the geometric mean sqrt(pq), the difference between pq and (p-1)(q-1) is roughly between 2 and 2.5 times the geometric mean. This kind of (or lack of) precision is likely useless for cryptography, but at least you can get a rough idea.
    Last edited by a moderator: May 5, 2017
  9. Dec 21, 2011 #8
    Thanks, Dodo! :D

    I was hoping for better precision, but I guess your's is the best there probably can be. Thanks anyway! :D
  10. Dec 21, 2011 #9
    You're welcome! Please keep in mind that there is a big "if" here.
    In some contexts, p and q are constructed in such a way that you have some guarantee that they will not be small factors. But what "not small" means... may not be very well defined.

    The idea above can be applied if you have some constraint on exactly how small the smallest factor can be. In general, if you call "p" the smallest factor, and if the ratio p/sqrt(pq) is, say, "x", then the difference between pq and (p-1)(q-1) will be (x + 1/x) sqrt(pq) - 1. What I wrote in the previous post was that, when "x" is 1, the coefficient (1 + 1/x) is 2, and when "x" is 0.5, then (1 + 1/x) is 2.5. The graph of (1+1/x) between x=0.1 and x=1 looks much like the one above; and, obviously, (1+1/x) can grow very quickly as "x" approaches 0 (when one of the factors is very small).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook