# Thread: Algebraïc Progression And Probabilities

1. ## 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 !

2. Sorry I made a mistake while writing the progression down, the second part of the progression involves modulo $n$.

3. Sorry, I realize now it should be $x_1 = a^2$ $(mod \ n)$