The period of Fibonacci numbers modulo $m$ is called Pisano period and its length is denoted as $\pi(m)$. Define the Pisano partition of $m$ as the set partition of the indices $\{0,1,\dotsc,\pi(m)-1\}$ based on the value of the corresponding terms in the Pisano period.
For example, for $m=3$, the Pisano period has length $\pi(3)=8$ and is formed by $$(0, 1, 1, 2, 0, 2, 2, 1).$$ Correspondingly, the Pisano partition of $3$ is $$\bigl\{\{0,4\},\{1,2,7\},\{3,5,6\}\bigr\}.$$
The sizes of Pisano partitions of $m=1,2,\dots$ are listed in OEIS A066853.
Call two positive integers equivalent iff their Pisano partitions are equal (hence, it's necessary that their Pisano period lengths are equal). I'd like to get some insight into this equivalence for prime numbers.
There exist many examples of equivalent primes. The smallest period length that admits such primes is $86$ with the pair of equivalent primes $6709$ and $144481$. In fact, they form the only equivalence class of primes with the period length 86. The next period length with nontrivial equivalence classes is $118$ with two equivalence classes: $\{709\}$, $\{8969, 336419\}$.
Q: Is there a simple characterization of equivalent primes? In particular, is there a way to test equivalence without computing the Pisano partition?
PS. It may be noticed that the smallest elements of non-singleton parts in the Pisano partition for the equivalent primes $6709$ and $144481$ form the set $\{0\} \cup \{2k+1 \mid 0\leq k\leq 20\}$. Similarly, the smallest elements of non-singleton parts in the Pisano partition for the equivalent primes $8969$ and $336419$ form the set $\{0\} \cup \{2k+1 \mid 0\leq k\leq 28\}$. Furthermore, we have the following relation to the period lengths: $20=\frac{86-6}4$ and $28=\frac{118-6}4$. I do not know if this pattern holds in general.
