# Thread: Integer factorization

1. ## Integer factorization

Suppose we have a huge number $n$ (in this case $n =20800309729538371074209$). We know that $n = pq$, where $p$ and $q$ are distinct primes. We also know that

$\phi(n)=20800309725991259351316$

How can we factorise $n$ using only the given information?

Attempt:
So, here's the equation for Euler's totient function of n to realate all we know:

$\phi(n)=n \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)$

I rearranged it to:

$\phi(n) . n = \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)$

I'm stuck here. What can I do after that to find out $p$ and $q$?

2. I don't really understand the way you rearranged $\phi(n)$

$\phi(n)=n \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)=n \frac{(p-1)(q-1)}{pq} = (p-1)(q-1) = n+1-(p+q)$

$p+q = n-\phi(n)+1$

3. Originally Posted by demode
Suppose we have a huge number $n$ (in this case $n =20800309729538371074209$). We know that $n = pq$, where $p$ and $q$ are distinct primes. We also know that

$\phi(n)=20800309725991259351316$

How can we factorise $n$ using only the given information?

Attempt:
So, here's the equation for Euler's totient function of n to realate all we know:

$\phi(n)=n \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)$

I rearranged it to:

$\phi(n) . n = \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)$

I'm stuck here. What can I do after that to find out $p$ and $q$?
See...

http://www.mathhelpforum.com/math-he...on-174405.html

... question b)...

Kind regards

$\chi$ $\sigma$