Constructability of sets of prime power congruences from factors of $(p^n-1)n$.

Question

Given a prime $p$ and a set $\mathcal{S}$ of relations $q_i\rightarrow q_j$ iff $q_i^{e_i}\mid q_j^{e_j}-1$, can I choose an $n\in \mathbb{N}$ so that among the factors of $(p^n-1)n$ is a set of powers of distinct primes that satisfies the relations in $\mathcal{S}$?

Notes:

• Once a power $e_i$ is chosen for a prime $q_i$, it is not allowed to vary - that is, $e_i$ is the power used in all comparisons. I prefer that it is the highest power dividing $p^n-1$.
• Is there an algorithmic/inductive way of constructing a minimal choice with respect to total order?

Answer 1

Here's an attempt at an answer after the clarifications in the comments. As noted above, this is impossible if $S$ contains directed cycles (since $q_i \to q_j$ implies $q_i^{e_i} < q_j^{e_j}$). Otherwise, I claim that we can take $e_i$ to be any desired positive integer.

Since $S$ has no cycles, we can re-index the relations so that $q_i \to q_j$ only occurs if $i \le j$. We choose $q_1$ to be any prime, and then inductively choose $q_j \equiv 1 \pmod {\prod_i q_i^{e_i}}$, the product taken over all $i$ such that $q_i \to q_j \in S$. Then also $q_j^{e_j} \equiv 1 \pmod{q_i^{e_i}}$, so $q_i$ and $q_j$ satisfy the desired relation.

If need be, we can refine this congruence class so that in addition to every relation in $S$ being satisfied, we also have $q_i \not\,\!\to q_j$ for any pair outside of $S$ (provided we didn't choose $q_1 = 2$, $e_1=1$).

Having chosen $q_i$ and $e_i$, it remains to take $n = \prod_i q_i^{e_i}$ so that $(p^n-1)n$ contains them as prime factors. I don't see why $p$ plays any role in the question as currently stated, except that it has a chance of adding additional copies of some $q_i$, and you've said this is not an issue.

I'm curious to see if the construction can be adjusted so that $q_i^{e_i} \parallel (p^n-1)n$ instead of just $q_i^{e_i} \parallel n$.