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

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?
-
 I don't understand the relations. Are the values of $e_i$ prescribed or allowed to vary? If they can be different for each $(i,j)$ pair, then the relations are trivial (just take $e_j$ large enough). On the other hand, if $e_i$ can only depend on $i$, then you will need to specify further conditions on $S$ (it certainly could not contain cycles). – Erick Wong Jul 1 '12 at 20:56 The values of $e_i$ are prescribed when the set of prime powers is selected - if you choose $q_i^{e_i}$, that is the $e_i$ which is always associated with that $q_i$ in every comparison. So, you are correct in that $\mathcal{S}$ cannot contain cycles. – Alexander Gruber Jul 2 '12 at 2:23 In that case, are we free to choose $e_i$ independently of $n$, or must it be the exact power of $q_i$ dividing $(p^n-1)n$? I would guess the latter, or else the value of $p$ seems irrelevant. – Erick Wong Jul 2 '12 at 2:32 The $e_i$ do not have to be the maximum power of $q_i$ dividing $(p^n-1)n$. I also think that the value of $p$ may indeed be irrelevant as a result, but I am not sure since I cannot prove that this can happen at all. If the case where I am allowed choose $p$ too can be proved, I would be satisfied with that. – Alexander Gruber Jul 2 '12 at 15:04

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$.
 Thanks. This is a good point (and a good solution). I think I need to revise my question somewhat, so that some factors must be in $p^n - 1$. I will think about this and add to the original post. – Alexander Gruber Jul 3 '12 at 19:23