Let $m, n \ge 2$ be integers. Carl is given $n$ marked points in the plane and wishes to mark their centroid.* He has no standard compass or straightedge. Instead, he has a device which, given marked points $A$ and $B$, marks the $m-1$ points that divide segment $\overline{AB}$ into $m$ congruent parts (but does not draw the segment).

For which pairs $(m,n)$ can Carl necessarily accomplish his task, regardless of which $n$ points he is given?

*Here, the [i]centroid[/i] of $n$ points with coordinates $(x_1, y_1), \dots, (x_n, y_n)$ is the point with coordinates $\left( \frac{x_1 + \dots + x_n}{n}, \frac{y_1 + \dots + y_n}{n}\right)$.

[i]Proposed by Holden Mui and Carl Schildkraut[/i]
1. **Define the Problem and Tools:**
   Carl is given \( n \) marked points in the plane and wishes to mark their centroid using a device that, given two points \( A \) and \( B \), marks the \( m-1 \) points that divide the segment \( \overline{AB} \) into \( m \) congruent parts. We need to determine for which pairs \( (m, n) \) Carl can necessarily accomplish his task.

2. **Define Key Terms:**
   - An \( m \)-device: A device that, given points \( A \) and \( B \), marks the \( m-1 \) points that divide \( \overline{AB} \) into \( m \) congruent parts.
   - \( m \)-obtainable: A point that can be marked using an \( m \)-device.
   - \( m \)-solvable: A set of \( n \) points is \( m \)-solvable if the centroid of the \( n \) points is \( m \)-obtainable.

3. **Claim 1:**
   - **Statement:** Let the points \( a_1, a_2, \ldots, a_n \) be given on the complex plane. Then all points of the form \( \frac{\sum_{i=1}^n d_i a_i}{2^k} \) where \( \sum_{i=1}^n d_i = 2^k \) and \( d_i \in \mathbb{N}_0 \) are 2-obtainable.
   - **Proof:** 
     - **Base Case:** For \( k = 0 \), it is trivial.
     - **Inductive Step:** Assume the result is true for \( k < m \). For \( k = m \), consider a point with denominator \( 2^m \):
       \[
       \frac{\sum_{i=1}^n \ell_i a_i}{2^m} \text{ where } \ell_1 \le \ell_2 \le \cdots \le \ell_n \text{ and } \sum_{i=1}^n \ell_i = 2^m
       \]
       Let \( j \) be the least number such that \( \sum_{i=1}^j \ell_i \ge 2^{m-1} \). Let \( \ell_j = k_j + p_j \) such that:
       \[
       \ell_1 + \ell_2 + \cdots + \ell_{j-1} + k_j = 2^{m-1}
       \]
       \[
       p_j + \ell_{j+1} + \ell_{j+2} + \cdots + \ell_n = 2^{m-1}
       \]
       Then:
       \[
       \frac{\sum_{i=1}^n \ell_i a_i}{2^m} = \frac{\frac{\ell_1 a_1 + \ell_2 a_2 + \cdots + \ell_{j-1} a_{j-1} + k_j a_j}{2^{m-1}} + \frac{p_j a_j + \ell_{j+1} a_{j+1} + \cdots + \ell_n a_n}{2^{m-1}}}{2}
       \]
       By the induction hypothesis, both terms are 2-obtainable, so the point is also 2-obtainable. This completes the induction.

4. **Claim 2:**
   - **Statement:** Let \( p \) be a prime. Then a set of \( p \) points is \( \text{rad}(2p) \)-solvable.
   - **Proof:**
     - If \( p = 2 \), it is trivial.
     - For odd \( p \), let \( \text{rad}(2p) = 2p \). Let the \( p \) points be \( a_1, a_2, \ldots, a_p \). Let \( m \) be the unique positive integer such that \( 2^{m+1} > p > 2^m \) and let \( p = 2^m + k \). Consider the points:
       \[
       A = \frac{2a_1 + 2a_2 + \cdots + 2a_{2^m-k} + a_{2^m-k+1} + \cdots + a_p}{2^{m+1}}
       \]
       \[
       B = \frac{(2^{m+1} - 2k)a_1 + (2^{m+1} - 2k)a_2 + \cdots + (2^{m+1} - k)a_{2^m-k+1} + \cdots + (2^{m+1} - k)a_p}{2^{2m+1}}
       \]
       By Claim 1, these points are 2-obtainable, hence \( 2p \)-obtainable. Then:
       \[
       \frac{2kA + 2^{m+1}B}{2p} = \frac{\sum_{i=1}^p a_i}{p}
       \]
       This shows the centroid is \( 2p \)-obtainable.

5. **Claim 3:**
   - **Statement:** A set of \( n \) points is \( \text{rad}(2n) \)-solvable.
   - **Proof:**
     - Let \( n = \prod_{i=1}^k p_i^{\alpha_i} \). We use induction on \( \Omega(n) = \sum_{i=1}^k \alpha_i \).
     - **Base Case:** Same as Claim 2.
     - **Inductive Step:** Partition the points into disjoint groups of \( p_1 \) points. The centroid of each group is \( \text{rad}(2n) \)-obtainable by Claim 2. Focus on the \( \frac{n}{p_1} \) centroids. By the induction hypothesis, the centroid of these centroids is \( \text{rad}(2n) \)-obtainable.

6. **Claim 4:**
   - **Statement:** If a set of \( n \) points is \( m \)-solvable, then \( 2 \mid m \).
   - **Proof:**
     - Assume \( m \) is odd. If \( n \) is even, the denominator of the centroid has a factor of 2, so \( m \) must be even, a contradiction. Thus, \( n \) must be odd.
     - Define a point \( \frac{\sum_{i=1}^n d_i a_i}{r} \) as *good* if at least one \( d_i \) is even. All \( m \)-obtainable points are good.
     - If \( P = \frac{\sum_{i=1}^n x_i a_i}{u} \) and \( Q = \frac{\sum_{i=1}^n y_i a_i}{v} \) are good, then:
       \[
       \frac{wP + (m-w)Q}{m} = \frac{\sum_{i=1}^n (x_i w v + y_i (m-w) u) a_i}{uvm}
       \]
       Since \( m \) is odd, one of \( w \) or \( m-w \) is even. Thus, the new point is also good.
     - The centroid \( \frac{a_1 + a_2 + \cdots + a_n}{m} \) is not good, so \( m \) must be even.

7. **Claim 5:**
   - **Statement:** If a set of \( n \) points is \( m \)-solvable, then \( \text{rad}(2n) \mid m \).
   - **Proof:**
     - Let \( p \) be a prime divisor of \( n \). If \( p \nmid m \), all \( m \)-obtainable points have denominators not divisible by \( p \). Since the centroid has denominator \( n \), \( p \mid m \). Combining this with Claim 4, we get \( \text{rad}(2n) \mid m \).

8. **Conclusion:**
   - Using Claims 3 and 5, we conclude that the solution pairs are \( (k \cdot \text{rad}(2n), n) \) where \( k \in \mathbb{N} \).

The final answer is \( \boxed{ (k \cdot \text{rad}(2n), n) } \) where \( k \in \mathbb{N} \).