Let $ m $ be a prime, $ n \in \mathbb{N} $, and $ A = \{a_1, a_2, \dots, a_n\} \subset \mathbb{Z}_m $ be a set of $ n $ distinct elements.
We seek to determine whether there exist $ x, d \in \mathbb{Z}_m $ such that the multiset $ \{x + kd \mod m \mid k = 0, 1, \dots, n-1\} $ equals $ A $ as a set.
---
**Formal Statement:**
Given:
- Prime modulus $ m \geq 2 $,
- Integer $ 1 \leq n \leq 10^5 $,
- Set $ A \subset \mathbb{Z}_m $, $ |A| = n $, with $ A = \{a_1, \dots, a_n\} $, all $ a_i $ distinct and $ 0 \leq a_i < m $.
**Question:**
Do there exist $ x, d \in \mathbb{Z}_m $ such that
$$
A = \left\{ x + kd \mod m \;\middle|\; k = 0, 1, \dots, n-1 \right\}?
$$
If yes, output any such pair $ (x, d) $ with $ 0 \leq x, d < m $.
If no, output $-1$.
---
**Equivalent Condition:**
The set $ A $ must be equal to an arithmetic progression modulo $ m $ of length $ n $, i.e., the elements of $ A $, when sorted in $ \mathbb{Z}_m $, must form a sequence where consecutive differences (in the cyclic modular sense) are constant, up to rotation and reflection.
Note: Since $ m $ is prime, $ \mathbb{Z}_m $ is a field, and for $ d \neq 0 $, the map $ k \mapsto x + kd \mod m $ is injective for $ k = 0, \dots, n-1 $ as long as $ n \leq m $, which holds.
Let $ S $ be the sorted list of elements of $ A $ in $ [0, m-1] $:
$ s_0 < s_1 < \dots < s_{n-1} $.
Let $ \Delta_i = s_{i+1} - s_i $ for $ i = 0, \dots, n-2 $, and $ \Delta_{n-1} = (s_0 + m) - s_{n-1} $ (the wrap-around gap).
Then $ A $ is an arithmetic progression modulo $ m $ if and only if all the $ \Delta_i $ are equal except possibly one, and that one (the wrap-around) equals $ n \cdot d - \sum_{i=0}^{n-2} \Delta_i $, and the non-wrap differences are all equal to $ d $.
But a better approach:
Let $ D $ be the multiset of differences $ (s_j - s_i) \mod m $ for $ i < j $. In an AP of length $ n $, the set of pairwise differences must be exactly $ \{ kd \mod m \mid 1 \leq k \leq n-1 \} $, each appearing exactly $ n - k $ times.
However, a simpler and more efficient characterization:
> A set $ A \subset \mathbb{Z}_m $ of size $ n $ is an arithmetic progression modulo $ m $ if and only if the multiset of differences $ \{ a_i - a_j \mod m \mid a_i > a_j \} $ consists of multiples of a single generator $ d $, and the number of distinct differences is exactly $ n-1 $, each appearing with multiplicity proportional to their step.
But the most practical method:
**Algorithmic Characterization (for formal output):**
Let $ S = \text{sorted}(A) $.
Let $ g = \gcd(\Delta_0, \Delta_1, \dots, \Delta_{n-2}, m) $, where $ \Delta_i = s_{i+1} - s_i $.
Then $ A $ is an AP modulo $ m $ if and only if:
1. All non-wrap differences $ \Delta_i $ for $ i = 0 $ to $ n-2 $ are equal to some $ d \in \mathbb{Z}_m $, **or**
2. There is exactly one "wrap-around" gap, i.e., one $ \Delta_i $ is large (greater than $ m/2 $), and all others are equal to some $ d $, and the wrap-around gap equals $ m - (n-1)d \mod m $.
Actually, the cleanest way:
Let $ d $ be the greatest common divisor of all pairwise differences $ (a_i - a_j) \mod m $, $ i \ne j $, in the additive group $ \mathbb{Z}_m $. Since $ m $ is prime, the subgroup generated by the differences is cyclic.
But even simpler:
Let $ S = \text{sorted}(A) $. Define the set of consecutive differences $ D = \{ s_{i+1} - s_i \mid i = 0, \dots, n-2 \} \cup \{ s_0 + m - s_{n-1} \} $.
Then $ A $ is an AP modulo $ m $ if and only if:
- All elements of $ D $ are equal to the same value $ d $, **except possibly one**, and that one equals $ m - (n-1)d \mod m $.
Wait — that’s not right.
Actually, in a linear AP modulo $ m $, the elements are $ x, x+d, x+2d, \dots, x+(n-1)d \mod m $.
When sorted in $ [0, m-1) $, the consecutive differences are either:
- All equal to $ d $, if the progression does not wrap around, or
- All equal to $ d $, except one difference which is $ d - m $ (i.e., a negative jump), which occurs when the progression wraps around.
But since we are sorting in $ [0, m) $, the wrap-around appears as a large gap: from $ s_{n-1} $ to $ s_0 + m $, so the wrap gap is $ s_0 + m - s_{n-1} $.
In a true AP modulo $ m $, the set of consecutive differences in the sorted list must consist of $ n-1 $ copies of $ d $, and one copy of $ m - (n-1)d $, but only if the progression wraps.
Actually, the sum of all consecutive differences in the circular sense must be $ m $:
$$
\sum_{i=0}^{n-1} \Delta_i = m
$$
where $ \Delta_i $ are the $ n $ gaps between consecutive elements in the circular sorted order.
In an arithmetic progression modulo $ m $, the $ n $ gaps are: $ n-1 $ gaps of size $ d $, and one gap of size $ m - (n-1)d $.
Thus, the multiset of gaps must contain $ n-1 $ copies of some $ d $, and one copy of $ m - (n-1)d $.
Therefore, the condition is:
Let $ S = \text{sorted}(A) $, and compute the $ n $ circular consecutive differences:
$$
\Delta_i =
\begin{cases}
s_{i+1} - s_i & \text{if } i < n-1 \\
s_0 + m - s_{n-1} & \text{if } i = n-1
\end{cases}
$$
Then $ A $ is an AP modulo $ m $ if and only if:
- Among the $ n $ values $ \Delta_0, \dots, \Delta_{n-1} $, exactly $ n-1 $ are equal to some $ d \in \mathbb{Z}_m $, and the remaining one is $ m - (n-1)d \mod m $.
Then:
- The common difference of the AP is $ d $.
- The first term $ x $ is the smallest element in the sequence **before** the large gap, i.e., if the large gap is between $ s_{n-1} $ and $ s_0 $, then $ x = s_0 $; otherwise, if the large gap is between $ s_k $ and $ s_{k+1} $, then the progression "wraps" and the first term is $ s_{k+1} $, and the progression is $ s_{k+1}, s_{k+2}, \dots, s_{n-1}, s_0, s_1, \dots, s_k $, so $ x = s_{k+1} $.
But since we can output any valid $ (x, d) $, we can do:
- If the large gap is between $ s_{n-1} $ and $ s_0 $, then $ x = s_0 $, $ d = \text{common difference} $.
- Else, if the large gap is between $ s_k $ and $ s_{k+1} $, then $ x = s_{k+1} $, $ d = \text{common difference} $.
But note: $ d $ must satisfy $ (n-1)d \equiv m - \text{large gap} \mod m $, and since the large gap is $ m - (n-1)d $, we have $ d = \frac{m - \text{large gap}}{n-1} \mod m $, provided $ n > 1 $.
If $ n = 1 $, then any $ x = a_1 $, $ d = 0 $ works.
So the formal algorithmic condition is:
---
**Formal Mathematical Condition:**
Let $ S = (s_0, s_1, \dots, s_{n-1}) $ be the sorted sequence of $ A $ in increasing order.
Define the circular consecutive differences:
$$
\Delta_i =
\begin{cases}
s_{i+1} - s_i & \text{for } 0 \leq i \leq n-2 \\
s_0 + m - s_{n-1} & \text{for } i = n-1
\end{cases}
$$
Let $ \delta = \min_{i \ne j} \Delta_i \ne \Delta_j $, i.e., let $ d $ be the value that appears $ n-1 $ times in $ \Delta_0, \dots, \Delta_{n-1} $, and let $ \Delta_{\text{large}} $ be the other value.
Then $ A $ is an arithmetic progression modulo $ m $ **if and only if**:
- $ n = 1 $, or
- $ n \geq 2 $ and $ \Delta_{\text{large}} \equiv m - (n-1)d \pmod{m} $, and $ d \ne 0 $, or
- $ d = 0 $ and $ n = 1 $ (trivial), or if $ d = 0 $ and $ n > 1 $, then all $ a_i $ equal — but $ A $ has distinct elements, so $ d \ne 0 $.
Since elements are distinct, $ d \ne 0 $.
So:
> $ A $ is an AP mod $ m $ iff the multiset $ \{ \Delta_0, \dots, \Delta_{n-1} \} $ contains exactly one value $ \Delta_{\text{large}} $ and $ n-1 $ copies of a single value $ d \in \mathbb{Z}_m \setminus \{0\} $, and $ \Delta_{\text{large}} \equiv m - (n-1)d \pmod{m} $.
Then, to recover $ x $:
Let $ j $ be the index such that $ \Delta_j = \Delta_{\text{large}} $.
Then the progression starts at $ s_{(j+1) \mod n} $, because the large gap follows $ s_j $, so the next element $ s_{(j+1) \mod n} $ is the start of the progression.
Thus, $ x = s_{(j+1) \mod n} $, and $ d $ is the common difference.
---
**Final Formal Output:**
Let $ S = \text{sorted}(A) $, $ n = |A| $.
Define $ \Delta_i $ for $ i = 0, \dots, n-1 $ as above.
Let $ d $ be the value that occurs $ n-1 $ times in $ \Delta $, and $ \Delta_{\text{large}} $ the other.
If $ n = 1 $:
Output $ (s_0, 0) $
Else if $ \Delta_{\text{large}} \equiv m - (n-1)d \pmod{m} $:
Let $ j $ be the index with $ \Delta_j = \Delta_{\text{large}} $
Let $ x = s_{(j+1) \mod n} $
Output $ (x, d) $
Else:
Output $ -1 $
Note: Since $ m $ is prime and $ d \ne 0 $, $ d $ has an inverse mod $ m $, so $ d = \frac{m - \Delta_{\text{large}}}{n-1} \mod m $ is well-defined if the condition holds.
But we don’t need to compute $ d $ from $ \Delta_{\text{large}} $ — we get $ d $ from the majority value.
So the above condition is sufficient and necessary.
---
**Final Mathematical Formulation:**
Let $ A \subset \mathbb{Z}_m $, $ |A| = n $, $ A $ distinct. Let $ S = (s_0 < s_1 < \dots < s_{n-1}) $ be the sorted elements of $ A $.
Define $ \Delta_i = \begin{cases} s_{i+1} - s_i & \text{if } i < n-1 \\ s_0 + m - s_{n-1} & \text{if } i = n-1 \end{cases} $
Let $ \mathcal{D} = \{ \Delta_0, \dots, \Delta_{n-1} \} $.
Then $ A $ is an arithmetic progression modulo $ m $ if and only if:
- $ n = 1 $, or
- $ n \geq 2 $, and $ \mathcal{D} $ contains exactly one distinct value $ \Delta_{\text{large}} $ appearing once, and another value $ d \in \mathbb{Z}_m \setminus \{0\} $ appearing $ n-1 $ times, and $ \Delta_{\text{large}} \equiv m - (n-1)d \pmod{m} $.
If this holds, then let $ j \in \{0, \dots, n-1\} $ be the unique index such that $ \Delta_j = \Delta_{\text{large}} $, and output $ x = s_{(j+1) \mod n} $, $ d $.
Otherwise, output $ -1 $.