Let $q=p^r$ for a prime number $p$ and positive integer $r$. Let $\zeta = e^{\frac{2\pi i}{q}}$. Find the least positive integer $n$ such that 
\[\sum_{\substack{1\leq k\leq q\\ \gcd(k,p)=1}} \frac{1}{(1-\zeta^k)^n}\]
is not an integer. (The sum is over all $1\leq k\leq q$ with $p$ not dividing $k$.)

[i]Victor Wang[/i]
1. **Define the problem and notation:**
   Let \( q = p^r \) for a prime number \( p \) and positive integer \( r \). Let \( \zeta = e^{\frac{2\pi i}{q}} \). We need to find the least positive integer \( n \) such that 
   \[
   \sum_{\substack{1 \leq k \leq q \\ \gcd(k, p) = 1}} \frac{1}{(1 - \zeta^k)^n}
   \]
   is not an integer. The sum is over all \( 1 \leq k \leq q \) with \( p \) not dividing \( k \).

2. **Cyclotomic polynomial and roots:**
   The \( \zeta^k \) are roots of the \( q \)-th cyclotomic polynomial \( \Phi_{p^r}(x) = x^{(p-1)p^{r-1}} + x^{(p-2)p^{r-1}} + \cdots + x^{p^{r-1}} + 1 \). By polynomial transformations, the \( \frac{1}{1 - \zeta^k} \) are the roots of 
   \[
   x^{(p-1)p^{r-1}} \Phi_{p^r}\left(1 - \frac{1}{x}\right) = \sum_{i=0}^{(p-1)p^{r-1}} \left(\sum_{j=0}^{p-1} \binom{jp^{r-1}}{i}\right)(-1)^i x^{(p-1)p^{r-1} - i}.
   \]
   Note that the \( x^{(p-1)p^{r-1}} \) coefficient is \( p \).

3. **Symmetric sums and key claim:**
   For \( 1 \leq k \leq (p-1)p^{r-1} \), define 
   \[
   T_k = \sum_{i=1}^{p-1} \binom{ip^{r-1}}{k}.
   \]
   The \( k \)-th symmetric sum of the \( \frac{1}{1 - \zeta^k} \) is \( \frac{1}{p} T_k \).

4. **Key claim:**
   We have \( p^{r-1} \mid kT_k \) for all \( k \). Moreover, \( \nu_p(kT_k) = r-1 \) is equivalent to \( k \geq (p-2)p^{r-1} + 1 \).

5. **Proof of the key claim:**
   We write 
   \[
   kT_k = \sum_{i=1}^{p-1} k \binom{ip^{r-1}}{k} = p^{r-1} \sum_{i=1}^{p-1} i \binom{ip^{r-1} - 1}{k - 1}.
   \]
   This immediately establishes \( p^{r-1} \mid kT_k \). Then, \( \nu_p(kT_k) > r-1 \) is equivalent to 
   \[
   p \mid \sum_{i=1}^{p-1} i \binom{ip^{r-1} - 1}{k - 1}.
   \]
   Let \( d_j \) be the digit in the \( p^j \) place of \( k-1 \) when it is written in base \( p \). By Lucas' theorem, we have 
   \[
   \sum_{i=1}^{p-1} i \binom{ip^{r-1} - 1}{k - 1} \equiv \sum_{i=1}^{p-1} i \binom{i - 1}{d_{r-1}} \prod_{j=0}^{r-2} \binom{p-1}{d_j} \equiv \left(\prod_{j=0}^{r-2} \binom{p-1}{d_j}\right) \left((d_{r-1} + 1) \sum_{i=1}^{p-1} \binom{i}{d_{r-1} + 1}\right) \pmod{p}.
   \]
   Since no \( \binom{p-1}{d_j} \) is divisible by \( p \), the condition is thus equivalent to 
   \[
   (d_{r-1} + 1) \sum_{i=1}^{p-1} \binom{i}{d_{r-1} + 1} = (d_{r-1} + 1) \binom{p}{d_{r-1} + 2} \equiv 0 \pmod{p},
   \]
   where the equality is by the hockey-stick identity. If \( d_{r-1} < p-2 \), then \( p \mid \binom{p}{d_{r-1} + 2} \implies \nu_p(kT_k) > r-1 \). On the other hand, if \( d_{r-1} = p-2 \), then the above quantity is nonzero modulo \( p \) and hence \( \nu_p(kT_k) = r-1 \). Note that \( d_{r-1} \leq p-2 \), since \( k \leq (p-1)p^{r-1} \) so the \( p^{r-1} \) place of \( k-1 \) is at most \( p-2 \).

6. **Important corollary:**
   From the above claim, we find that \( p \mid T_k \) if \( k \leq (p-2)p^{r-1} \) since \( \nu_p(k) \leq r-1 \) but \( \nu_p(kT_k) \geq r \). Additionally, \( p \mid T_k \) if \( (p-2)p^{r-1} + 1 \leq k \leq (p-1)p^{r-1} - 1 \), since \( \nu_p(k) \leq r-2 \) but \( \nu_p(kT_k) = r-1 \). But when \( k = (p-1)p^{r-1} \), we have \( \nu_p(k) = \nu_p(kT_k) = r-1 \). In conclusion, \( p \mid T_k \) for all \( k \) except \( k = (p-1)p^{r-1} \).

7. **Power sums and Newton's Identities:**
   We are interested in the power sums of the \( \frac{1}{1 - \zeta^k} \). To that end, we will employ Newton's Identities in the following form. Let \( S_i \) denote the \( i \)-th power sum of the \( \frac{1}{1 - \zeta^k} \) (the sum of their \( i \)-th powers) for \( i \geq 1 \). Then for \( i \leq (p-1)p^{r-1} \) we have 
   \[
   S_i = \left(\sum_{j=1}^{i-1} \frac{(-1)^{j+1}}{p} T_j S_{i-j}\right) + \frac{(-1)^{j+1}}{p} i T_i,
   \]
   and for \( i > (p-1)p^{r-1} \) we have 
   \[
   S_i = \sum_{j=1}^k \frac{1}{(-1)^{j+1}} \sigma_j S_{i-j}.
   \]
   From the above, the only prime \( q \) where we could ever have \( \nu_q(S_i) < 0 \) is \( q = p \), since we only ever divide by \( p \). Hence it suffices to find the least \( n \) where \( \nu_p(S_n) < 0 \).

8. **Induction and divisibility:**
   According to our claim and corollary, straightforward induction implies that for \( 1 \leq i \leq (p-2)p^{r-1} \), \( S_i \) will be divisible by \( p^{r-1} \), but we will have \( \nu_p(S_{(p-2)p^{r-1} + 1}) = r-2 \). Then induction again implies that for \( (p-2)p^{r-1} \leq i \leq (p-1)p^{r-1} \), \( S_i \) will be divisible by \( p^{r-2} \).

9. **Final steps and conclusion:**
   For brevity, let \( t = (p-1)p^{r-1} \). Fix some \( i > t \); by our corollary, if \( p^\ell \mid S_{i-j} \) for \( 1 \leq j \leq t-1 \) and \( p^{\ell+1} \mid S_{i-t} \), then \( p^\ell \mid S_i \). However, if \( p^\ell \mid S_{i-j} \) for \( 1 \leq j \leq t-1 \) and \( \nu_p(S_{i-t}) \leq \ell \), then \( \nu_p(S_i) = \nu_p(S_{i-t}) - 1 \).

   Applying this fact, it follows that:
   - \( p^{r-2} \) divides \( S_i \) for \( (p-2)p^{r-1} + 1 + 0(p-1)p^{r-1} \leq i \leq (p-2)p^{r-1} + 1(p-1)p^{r-1} \),
   - \( \nu_p(S_i) = r-3 \) when \( i = (p-2)p^{r-1} + 1 + 1(p-1)p^{r-1} \), since we know \( p^{r-2} \mid S_{i-j} \) for \( 1 \leq j \leq (p-1)p^{r-1} - 1 \), but \( \nu_p(S_{i-(p-1)p^{r-1}}) = r-2 \),
   - \( p^{r-3} \) divides \( S_i \) for \( (p-2)p^{r-1} + 1 + 1(p-1)p^{r-1} \leq i \leq (p-2)p^{r-1} + 2(p-1)p^{r-1} \),
   - \( \nu_p(S_i) = r-4 \) when \( i = (p-2)p^{r-1} + 1 + 2(p-1)p^{r-1} \), since we know \( p^{r-3} \mid S_{i-j} \) for \( 1 \leq j \leq (p-1)p^{r-1} - 1 \), but \( \nu_p(S_{i-(p-1)p^{r-1}}) = r-3 \),
   - \( p^{r-4} \) divides \( S_i \) for \( (p-2)p^{r-1} + 1 + 2(p-1)p^{r-1} \leq i \leq (p-2)p^{r-1} + 3(p-1)p^{r-1} \),
   - \( \nu_p(S_i) = r-5 \) when \( i = (p-2)p^{r-1} + 1 + 3(p-1)p^{r-1} \), since we know \( p^{r-4} \mid S_{i-j} \) for \( 1 \leq j \leq (p-1)p^{r-1} - 1 \), but \( \nu_p(S_{i-(p-1)p^{r-1}}) = r-4 \), and so on.

   Thus, the least \( i \) with \( \nu_p(S_i) \leq t \) is \( (p-2)p^{r-1} + 1 + (r-t-2)(p-1)p^{r-1} \). Plugging in \( t = -1 \) yields the advertised answer.

The final answer is \( \boxed{(p-2)p^{r-1} + 1 + (r-1)(p-1)p^{r-1}} \)