1
$\begingroup$

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?

Thanks in advance

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

1 Answer 1

3
$\begingroup$

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}}*)
$\endgroup$
4
  • 2
    $\begingroup$ +1 If you also include that p and q are ordered (e.g., p > q), you won't get the redundant solution. $\endgroup$
    – Bob Hanlon
    Sep 29 at 13:52
  • $\begingroup$ 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. $\endgroup$ Oct 1 at 21:54
  • 1
    $\begingroup$ @userrandrand This trick is known as Vieta's formula en.wikipedia.org/wiki/Vieta%27s_formulas $\endgroup$
    – yarchik
    Oct 2 at 19:43
  • $\begingroup$ 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. $\endgroup$ Oct 2 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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