Results 1 to 3 of 3

Thread: 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 :

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

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

    Question : what is the probability that a number $\displaystyle a$ picked at random in its interval generates a sequence in which $\displaystyle x_m$, with $\displaystyle m < \ln^2(n)$, shares a common factor with $\displaystyle n$ ? You may express your answer in terms of $\displaystyle a$, $\displaystyle n$, and $\displaystyle p_n$ (where $\displaystyle p_n$ is the n'th prime factor of $\displaystyle 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 $\displaystyle n$, but I just don't know where to start the answer .

    Thanks a lot !
    Last edited by Bacterius; Dec 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 $\displaystyle 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 $\displaystyle x_1 = a^2$ $\displaystyle (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: Oct 7th 2011, 12:18 PM
  2. Replies: 3
    Last Post: Sep 22nd 2011, 09:46 AM
  3. Approximate joint probabilities using marginal probabilities
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Jun 23rd 2011, 04:04 AM
  4. Replies: 8
    Last Post: Mar 23rd 2009, 07:26 AM
  5. probabilities
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Jun 10th 2008, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum