Number of $n \to p \bmod n$ before getting to 0

Let us remove the constraint that $p$ is a prime number. Given a strictly decreasing sequence $1=a_0 < a_1 < \ldots < a_k$ and consider the set

$$ S(\textbf{a}) := \{p: p \equiv a_j \pmod{a_{j+1}} \ \ \forall j = 0 \ldots k-1\} $$

This is exactly the set of numbers that will produce the sequence $\textbf{a}$ during this process. Note that this set is stable for shifting by $\text{lcm }\{ a_1, \ldots, a_k\}$, and that the set of solutions is determined by applying the chinese remainder theorem.

We will consider two particular sequences to get the following result: (1) there exist arbitrarily large (prime) numbers that ends in $2$ iterations; (2) there exist arbitrarily large numbers that ends in at least (about) $(\log p) /2 $ iterations.

For the first just consider the sequence $3>1$ and take a (prime) number $p\equiv 1 \pmod{3}$.

The second is more interesting. Consider the sequence $k > \ldots > 1$. This means that we have $p$ such that $p\equiv m-1 \equiv -1 \pmod{m}$ for all $m\le k$. Solutions of this system are exactly numbers that are $\equiv -1$ modulo $L_k:= \text{lcm}\{1, \ldots, k\}$. The smallest such positive number is exactly $L_k -1$. We can give an estimate of $\log L_k$ as starting from the equation

$$ L_k = \prod_{p \le k} p^{[\log k/\log p]}$$

Indeed, any prime will appear with the maximum exponent it can appear with. Taking the logarithm we get

$$ \log L_k = \sum_{p\le k} (\log p) [\log_p k] \le \sum_{p \le k} (\log p) (\log_p k +1) $$ $$ = \sum_{p\le k} \log k + \log p \le \sum_{p\le k} 2 \log k \approx (2 \log k) \frac{k}{\log k} = 2k $$

Using the prime counting theorem $|\{p\le k\}| \approx k/\log k$. Recall that $k$ is the number of iterations relative to the input number $p=L_k-1$. Thus we get $$( \log p )/2 \approx ( \log L_k)/2 < k$$

Giving the desired solution.