Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
You know the sum and product of $p$ and $(-q)$, so there is a quadratic equation that has those as roots. –  zyx Nov 14 '12 at 4:00

1 Answer 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.

share|improve this answer
    
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. –  Derek Nov 14 '12 at 4:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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