Let $n>1$ be a positive integer and $\mathcal S$ be the set of $n^{\text{th}}$ roots of unity. Suppose $P$ is an $n$-variable polynomial with complex coefficients such that for all $a_1,\ldots,a_n\in\mathcal S$, $P(a_1,\ldots,a_n)=0$ if and only if $a_1,\ldots,a_n$ are all different. What is the smallest possible degree of $P$?

[i]Adam Ardeishar and Michael Ren[/i]
1. **Understanding the Problem:**
   We need to find the smallest possible degree of an \( n \)-variable polynomial \( P \) with complex coefficients such that \( P(a_1, \ldots, a_n) = 0 \) if and only if \( a_1, \ldots, a_n \) are all different \( n \)-th roots of unity.

2. **Roots of Unity:**
   Let \( \zeta \) be a primitive \( n \)-th root of unity. The \( n \)-th roots of unity are \( \zeta^0, \zeta^1, \ldots, \zeta^{n-1} \).

3. **Polynomials \( R_k \):**
   Define the polynomials \( R_k(x_1, \ldots, x_n) = \sum_{j=1}^n x_j^k \). These polynomials will be used to construct \( P \).

4. **Lemma 0:**
   For all positive integers \( k < n \), it holds that \( \zeta_1^k + \zeta_2^k + \cdots + \zeta_n^k = 0 \).

5. **Lemma 1:**
   If \( a_1, \ldots, a_n \in \mathcal{S} \), then \( R_k(a_1, \ldots, a_n) = 0 \) for all \( k \) in \( D \) (the set of positive proper divisors of \( n \)) if and only if \( a_1, \ldots, a_n \) are pairwise distinct.

   **Proof of Lemma 1:**
   - If \( a_1, \ldots, a_n \) are pairwise distinct, then \( R_k(a_1, \ldots, a_n) = 0 \) for all \( k < n \) by Lemma 0.
   - Conversely, write \( a_j = \zeta^{e_j} \) for \( 0 \leq e_j < n \). Let \( R(x) = x^{e_1} + x^{e_2} + \cdots + x^{e_n} \). Since \( R(\zeta^k) = R_k(a_1, \ldots, a_n) = 0 \) for all \( k \in D \), \( R \) is divisible by every cyclotomic polynomial \( \Phi_{n/k} \) for \( k \in D \). Thus, \( R \) is divisible by their product:
     \[
     \prod_{k \in D} \Phi_{n/k} = \frac{x^n - 1}{x - 1} = 1 + x + \cdots + x^{n-1}.
     \]
   - Since \( \deg R \leq n - 1 \) and \( R(1) = n \), it follows that \( R(x) = 1 + x + \cdots + x^{n-1} \), implying \( a_1, \ldots, a_n \) are pairwise distinct.

6. **Constructing \( P \):**
   Consider the polynomial:
   \[
   P(t, x_1, \ldots, x_n) = \sum_{k \in D} t^k R_k(x_1, \ldots, x_n).
   \]
   For \( a_1, \ldots, a_n \in \mathcal{S} \), \( P(t, a_1, \ldots, a_n) \) is a polynomial in \( t \). By Lemma 1, this polynomial vanishes identically if and only if \( a_1, \ldots, a_n \) are pairwise distinct.

7. **Degree of \( P \):**
   The degree of \( P \) is determined by the largest proper divisor \( d \) of \( n \). Alternatively, it is \( \frac{n}{p} \), where \( p \) is the smallest prime divisor of \( n \).

8. **Verification:**
   - **First Approach (Allen Liu):**
     Suppose \( \deg P < d \). Consider the polynomial:
     \[
     Q(y_1, \ldots, y_p) = \sum_{j=1}^p P(\zeta_j y_j, \zeta_{p+j} y_j, \ldots, \zeta_{p(d-1)+j} y_j).
     \]
     If \( b_1, \ldots, b_p \in \mathcal{T} \) (the set of \( d \)-th roots of unity), then \( Q(b_1, \ldots, b_p) = 0 \). By Lemma 2, \( Q \) vanishes identically, leading to a contradiction.

   - **Second Approach (Authors):**
     Let \( \mathcal{P} \) be the set of polynomials of the form \( \sum_{k=1}^{n-1} Q_k R_k \) with \( \deg P < n \). Using Lemma 3 and Lemma 4, we show that \( \mathcal{P} = \mathcal{Q} \), the set of polynomials vanishing on all permutations of \( \zeta_1, \ldots, \zeta_n \). This leads to a contradiction if \( \deg P < d \).

Conclusion:
The smallest possible degree of \( P \) is the largest proper divisor \( d \) of \( n \), or equivalently \( \frac{n}{p} \), where \( p \) is the smallest prime divisor of \( n \).

The final answer is \( \boxed{\frac{n}{p}} \) where \( p \) is the smallest prime divisor of \( n \).