0

Question: Suppose that n is the product of distinct primes p and q, so n=pq

Show that p and q are the roots of the quadratic equation

x^2 -(n+1 -φ(n))x + n

Hence if n and φ(n) are known then n can be easily factored.

So far I know that φ(n)=(p-1)(q-1) and that φ(n)= #{1≤x≤n : gcd(x,n)=1}

Any guidance on how to proceed to start generating this quadratic would be greatly appreciated!

AnalysisisKey
  • 199
  • 2
  • 12

1 Answers1

1

In general, when $A,B$ are the roots of $x^2 + ax + b = 0$, we know that $(x-A)(x-B) = x^2 + ax + b$, and so $x^2 - (A+B)x + AB = x^2 + ax + b$ (for all $x$), so that $a = -(A + B), b = AB$, or $A+B = -a, AB = b$. So the coefficients of the quadratic are just the negative sum of the roots, and their product respectively.

When $n = pq$, we know that $\phi(n) = (p-1)(q-1) = pq - (p+q) + 1 = n - (p+q) + 1$. Hence $p+q = n - \phi(n) + 1$, and so we know that $p,q$ are the roots of $x^2 - (p+q) + pq = x^2 - (n + 1 - \phi(n)) + n$.

Henno Brandsma
  • 242,131
  • Thank you it should have occurred to me roots of polynomial equations that the sum of the roots say alpha and beta is equal to -b/a and the product is equal to c/a where the coefficients are a,b,c i.e ax^2+bx+c thank you for reminding me :) – AnalysisisKey Nov 27 '14 at 23:14