1. ## Integer factorization

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

$\displaystyle \phi(n)=20800309725991259351316$

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

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

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

I rearranged it to:

$\displaystyle \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 $\displaystyle p$ and $\displaystyle q$?

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

$\displaystyle \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)$

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

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

$\displaystyle \phi(n)=20800309725991259351316$

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

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

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

I rearranged it to:

$\displaystyle \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 $\displaystyle p$ and $\displaystyle q$?
See...

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

... question b)...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$