Results 1 to 3 of 3

Math Help - Algebra´c Progression And Probabilities

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Algebra´c Progression And Probabilities

    Okay, I wasn't sure where to post this, because it involves number theory, but since I am asking a question about probabilities, and I think it is fairly simple (I am not a star in prob's), I guess it belongs here.

    Say we have the progression :

    x_1 = a^2 \ mod \ n
    x_{m + 1} = (x_m + a)^2 \ mod \ n

    With n a composite number (for instance 35 = 5 \times 7), and a a positive integer in \sqrt{n} \leq a < n.

    Question : what is the probability that a number a picked at random in its interval generates a sequence in which x_m, with m < \ln^2(n), shares a common factor with n ? You may express your answer in terms of a, n, and p_n (where p_n is the n'th prime factor of n)

    I am really stumped on this question, there is a lot of information and I don't know where to start. I think it might be useful to use the prime factors of n, but I just don't know where to start the answer .

    Thanks a lot !
    Last edited by Bacterius; December 6th 2009 at 08:15 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Sorry I made a mistake while writing the progression down, the second part of the progression involves modulo n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Sorry, I realize now it should be x_1 = a^2 (mod \ n)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arithmetic algebraic progression
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 7th 2011, 12:18 PM
  2. Replies: 3
    Last Post: September 22nd 2011, 09:46 AM
  3. Approximate joint probabilities using marginal probabilities
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 23rd 2011, 04:04 AM
  4. Replies: 8
    Last Post: March 23rd 2009, 07:26 AM
  5. probabilities
    Posted in the Statistics Forum
    Replies: 3
    Last Post: June 10th 2008, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum