Results 1 to 2 of 2

Math Help - knowledge of n and phi(n) allows factoring of n

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    47

    knowledge of n and phi(n) allows factoring of n

    How would one factor a product of two primes (n), if they know both n and phi(n)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Let n = p_1p_2 \ \Leftrightarrow \ p_2 = \frac{n}{p_1} \qquad {\color{red}\star}.

    Then: \varphi (n) = \varphi (p_1p_2) = \varphi(p_1)\varphi(p_2) = (p_1 - 1)(p_2 - 1)

    So we have: \varphi (n) = (p_1 - 1) (\frac{n}{p_1}-1) by {\color{red}\star}

    All that we have to do now is solve for p_1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. I need some background knowledge on linear algebra?
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: September 28th 2010, 06:57 PM
  2. Flawed Knowledge of Reduction Formulas
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 26th 2010, 06:23 PM
  3. integrating by assumed knowledge
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 15th 2008, 04:30 PM
  4. knowledge q.
    Posted in the Statistics Forum
    Replies: 0
    Last Post: September 27th 2008, 09:14 AM

Search Tags


/mathhelpforum @mathhelpforum