1
$\begingroup$

I was also given these:
$p+q=n-\phi(n)+1$
$p-q=\sqrt((p+q)^2-4n)$
$\phi(n)=(p-1)(q-1)$
$p>q$

I've been trying to manipulate this as a system of equations, but it's just not working out for me. I found a similar problem on this site, but instead of $pq$ and $p-q$ being known, it had $pq$ and $\phi(pq)$, so that didn't help. The $\phi(n)$ function has never been mentioned in this class before, so I can't use any definitions of it (aside from the one given above) without proving them. Could someone please point me in the right direction here?

  • 1
    You know the sum and product of $p$ and $(-q)$, so there is a quadratic equation that has those as roots.2012-11-14

1 Answers 1

1

We have $(p+q)^2=(p-q)^2+4pq.$ Calculating the right-hand side is very cheap. Then calculating $p+q$ is cheap, a mild variant of Newton's Method. Once we know $p+q$ and $p-q$, calculating $p$ and $q$ is very cheap.

  • 0
    Unfortunately, I don't understand how to use Newton's method. However, I tried zyx's approach and that seems to be working, so I'm going to stick to that. Thanks to both of you for helping.2012-11-14