How many prime numbers can satisfy $p_{1}|p_{2}^{2}-1,..., p_{n-1}|p_{n}^{2}-1, p_{n}|p_{1}^{2}-1$?

Question

The problem is as follows:

Find all natural numbers $ n$ for which $ n$ primes $p_{1},p_{2},p_{3},...,p_{n}$ exist, such that $p_{1}|p_{2}^{2}-1,..., p_{n-1}|p_{n}^{2}-1, p_{n}|p_{1}^{2}-1$.

I've tried to look the the specific recursion without the prime number constraint, but I haven't been able to find anything useful to the problem. Do I try to find the specific primes or can I get around that a find $n$ directly?

Thank you for your insights.

Answer 1

Hint: Consider primes $p,q$ for which $p|q^2-1$. This means that $p|q-1$ or $p|q+1$; in particular, $p$ is at most $q+1$, and is actually much less if $q+1$ isn't prime (which it usually isn't, being even if $q$ is even). As a result, we should expect $p_i<p_{i+1}$ most of the time; see if you can turn this into a somewhat explicit description of what such sequences $(p_1,\dots,p_n)$ should look like.

Answer 2

If any prime is $2$ then suppose $p_n=2$. Then $p_{n-1}|2^2-1=3$ and so $p_{n-1}=3$. Repeating this process, $p_{n-2}|3^2-1=8$ and so $p_{n-2}=2$.

So one solution is the cycle $(2,3)$ for $n=2$.

Now suppose all $p_i$ are odd. But then $$p_i|(p_{i+1}-1) \left( \frac{p_{i+1}+1}{2}\right)$$ and so $p_i<p_{i+1}$ for all $i$ and so the sequence can never cycle round. There is only one solution.