Find prime numbers two prime numbers given a certain constraint

The question is: Find primenumbers p and q if n=pq=39247771 and φ(n) = 39233944.

Does anyone have an idea of how to approach this problem in mathematica?

• FactorInteger[39247771] is sufficient. Sep 29 at 9:47
• @yarchik ... and FactorInteger evaluates in couple seconds still for a product of two 25-digit primes, but becomes somewhat tedious above that. Sep 29 at 9:55
• @kirma yes, therefore see my answer below Sep 29 at 9:55

If $$n$$ is the product of two distinct primes, $$p$$ and $$q$$, then $$\varphi(n) = (p-1)(q-1) = pq -p -q +1 = n -p -q +1$$ which is enough information to find the factorization. I.e., you know $$pq=n$$ and $$p+q = n+1-\varphi(n)$$.

You can therefore use:

n = 39247771;
phi= 39233944;
Solve[p q == n && p + q == n + 1 - phi, {p, q}]
(*{{p -> 3989, q -> 9839}, {p -> 9839, q -> 3989}}*)

• +1 If you also include that p and q are ordered (e.g., p > q), you won't get the redundant solution. Sep 29 at 13:52
• Just mentioning a math trick that has been useful to me for those reading, if the sum S and product P of two numbers are known, then they are the roots of the polynomial equation: X^2-SX+P=0 via the root-coefficient relationship of polynomials. Oct 1 at 21:54
• @userrandrand This trick is known as Vieta's formula en.wikipedia.org/wiki/Vieta%27s_formulas Oct 2 at 19:43
• oh that's the name ! I wondered what the name was when I was writing that comment. I actually ended up checking that the fastest way to find p and q in the question was either applying Vieta's formula and using the general formula for the roots of degree 2 polynomials or using Reduce with the second degree polynomial. I am not sure why Solve with the product and sum system was slower. Oct 2 at 20:06