Results 1 to 2 of 2

Math Help - number theory problem...

  1. #1
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Post number theory problem...

    Please help in finding the factor of ...618240007109027021 by the p-1 method...

    thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Vedicmaths View Post
    Please help in finding the factor of ...618240007109027021 by the p-1 method...
    thanks a lot!
    n = 618240007109027021

    Select a bound for the factorial.
    bound =  \ln(n) is an acceptable limit.

    In this case about 43 .
    The exponent will be 43! (factorial of 43)

    Choose some number to raise to that exponential value. Any number (a) from 2 to n-1 is useable.
    You may want to check that \gcd(a,n)=1.
    2 is ok.


     r = ( 2^{43!}\mod n )

     f = \gcd(r-1,n)

    If
    1<f<n
    then you have a factor of n
    If not then raise the bound limit.

    In this case one of the factors is a 9 digit number.
    The first 3 digits and the last 3 digits are
    250___201

    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number Theory Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 28th 2009, 03:44 PM
  2. number theory problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: March 11th 2009, 08:43 AM
  3. Number Theory problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 30th 2008, 01:07 PM
  4. Replies: 2
    Last Post: December 18th 2008, 06:28 PM
  5. Number Theory GCD Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 10th 2006, 05:59 PM

Search Tags


/mathhelpforum @mathhelpforum