5
$\begingroup$

Given a prime number $p$ and an integer $0<a_0<p$. Consider a sequence $a_i=p \mod a_{i-1}$. How to estimate the smallest $i$ where $a_i=1$?

I tried some prime numbers, and found that such $i$ is always small. I have never found an $i$ larger than 50 when $p$ is smaller than $10^7$. How to estimate the upper bound of $i$?

$\endgroup$
7
  • 1
    $\begingroup$ If $a_i=1$, then $a_{i+1}=0$, and $a_{i+2}$ is undefined, so the smallest $i$ such that $a_i=1$ is the only $i$ such that $a_i=1$. Or do you mean the smallest $i$ as you vary $a_0$, keeping $p$ fixed? $\endgroup$ Feb 6, 2018 at 11:26
  • $\begingroup$ I had the same question. Probably my edit was not useful. There is a unique $i$ such that $a_i=1$. Do you want a bound on $i$ depending on $p$ and $a_0$ or only on $p$? The latter would rather be the "largest" $i$ for a fixed $p$ and varying $a_0$. $\endgroup$ Feb 6, 2018 at 11:39
  • $\begingroup$ I mean the only $i$ such that $a_i=1$. In fact, I just wonder why such $i$ are always small, for any $p$ and $a_0$. I guess such $i$ is equal to $O(\log p)$, for example. $\endgroup$
    – zbh2047
    Feb 6, 2018 at 12:43
  • $\begingroup$ I want a bound which only depends on $p$. That is, for any $0<a_0<p$, the bound is always correct. Your understanding and modification is really helpful. Thanks! $\endgroup$
    – zbh2047
    Feb 6, 2018 at 12:48
  • 3
    $\begingroup$ Jeffrey Shallit has asked essentially the same question (with partial results and a cash prize) here: mathoverflow.net/questions/164129/… $\endgroup$ Feb 7, 2018 at 21:05

1 Answer 1

1
$\begingroup$

This is a long comment rather than an answer.

Let $p$ be a prime. Consider the map $f(a)$ which assigns to $0<a<p$ the remainder of $p$ modulo $a$. The questions asks when the sequence $a$, $f(a)$, $f(f(a))$,... reaches $1$ for a starting $1<a<p$. Let $I(p)$ be the length of the longest such sequence as $a$ varies in $1<a<p$. The question asks for an upper bound on $I(p)$.

In average, we expect that $f(a)$ is half of $a$. So we should expect sort of $\log_2(p)$ steps in $a$, $f(a)$, $f(f(a))$, ... to reach $1$.

We can look at it the other way. What are the $a$ such that $f(a)=b$? Any such $a$ will be a divisor of $p-b$. Now we build a tree with root $1$. The branches to $1$ are all divisors of $p-1$ except $1$. Repeatedly, we put above any $b$ so far added to the tree all the divisors of $p-b$ which did not yet appear. The length of the longest path from the root is $I(p)$.

Since there are at most $\log_2(p)$ branches above each number, one gets (if I got that right) that $I(p)> C \log(p)/\log\log(p)$. On the other hand we expect less than $\log(p)$ branches in average, that would again confirm that $I(p)$ might be bounded by something like $O(\log(p))$. But I am not certain; it might be larger. Most likely though the averge of $I(p)$ is logarithmic in $p$.

This also illustrates that primes $p$ where $\tfrac{p-1}{2}$ is a Sophie Germain prime are likely to have a larger $I(p)$ while $p$ where $p-1$ has many factors should have smaller $I(p)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.