Results 1 to 3 of 3

Math Help - Integer factorization

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    225

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by demode View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: August 3rd 2010, 03:16 AM
  2. [Factorization] Factorization of polynomials
    Posted in the Algebra Forum
    Replies: 9
    Last Post: April 9th 2010, 12:15 AM
  3. Replies: 2
    Last Post: March 4th 2010, 01:49 AM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 12:20 PM
  5. Integer factorization
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 15th 2009, 02:27 PM

Search Tags


/mathhelpforum @mathhelpforum