Problem: 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 \le k \le 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$.)

\end{enumerate}

Solution: Let $S_q$ denote the set of primitive $q$th roots of unity (thus,
the sum in question is a sum over $S_q$).
\paragraph{Solution 1 (author).}
Let $\zeta_p=e^{2\pi i/p}$ be a fixed primitive $p$th root of unity. Observe
that the given sum is an integer for all $n\leq 0$ (e.g.  because the sum is an
integer symmetric polynomial in the primitive $q$th roots of unity). By
expanding polynomials in the basis $(1-x)^{k}$, it follows that if the sum in
the problem statement is an integer for all $n < n_0$, then
\[\sum_{\omega\in S_q} \frac{f(\omega)}{(1-\omega)^{n}}\in \ZZ\]
for all $n < n_0$ and $f\in \ZZ[x]$, whereas for $n=n_0$ there is some
$f\in \ZZ[x]$ for which the sum is not an integer (e.g. $f=1$).

Let $z_q=r\phi(q)-q/p=p^{r-1}[r(p-1)-1]$. We claim that the answer is $n =
z_q+1$.  We prove this by induction on $r$. First is the base case $r=1$.

\begin{lemma*}
  There exist polynomials $u,v\in \ZZ[x]$ such that
  $(1-\omega)^{p-1}/p = u(\omega)$ and $p/(1-\omega)^{p-1} = v(\omega)$ for all
  $\omega\in S_p$.

  (What we are saying is that $p$ is $(1-\omega)^{p-1}$ times a \emph{unit}
  (invertible algebraic integer), namely $v(\omega)$.)
\end{lemma*}

\begin{proof}
  Note that $p = (1-\omega)\dotsm(1-\omega^{p-1})$. Thus we can write
  \begin{align*}
    \frac{p}{(1-\omega)^{p-1}} &=
    \frac{1-\omega}{1-\omega} \cdot\frac{1-\omega^2}{1-\omega} \dotsm
    \frac{1-\omega^{p-1}}{1-\omega}
  \end{align*}
  and take
  \[v(x)=\prod_{k=1}^{p-1}\frac{1-x^{k}}{1-x}.\]
  Similarly, the polynomial $u$ is
  \[u(x) = \prod_{k=1}^{p-1}\frac{1-x^{k\ell_k}}{1-x^k}\]
  where $\ell_k$ is a multiplicative inverse of $k$ modulo $p$.
\end{proof}

Now, the main idea: given $g\in \ZZ[x]$, observe that \[S = \sum_{\omega
\in S_p} (1-\omega)g(\omega)\] is divisible by $1-\zeta_p^k$ (i.e. it is
$1-\zeta_p^k$ times an algebraic integer) for every $k$ coprime to $p$.  By
symmetric sums, $S$ is an integer; since $S^{p-1}$ is divisible by
$(1-\zeta_p)\dotsm(1-\zeta_p^{p-1}) = p$, the integer $S$ must itself be
divisible by $p$. (Alternatively, since $h(x) := (1-x)g(x)$ vanishes at
$x=1$, one can interpret $S$ using a roots of unity filter: $S = p\cdot h([x^0]
+ [x^p] + \dotsb) \equiv 0\pmod{p}$.) Now write
\[
\ZZ
\ni \frac{S}{p}
= \sum_{\omega \in S_p} \frac{(1-\omega)^{p-1}}{p} \frac{g(\omega)}{(1-\omega)^{p-2}}
= \sum_{\omega \in S_p} u(\omega)\frac{g(\omega)}{(1-\omega)^{p-2}}.
\]
Taking $g = v\cdot (1-x)^k$ for $k\geq 0$, we see that the sum in the
problem statement is an integer for any $n\leq p-2$.

Finally, we have
\[\sum_{\omega\in S_p}\frac{u(\omega)}{(1-\omega)^{p-1}}=\sum_{\omega\in
S_p}\frac{1}{p}=\frac{p-1}{p}\notin\ZZ,\]
so the sum is not an integer for $n=p-1$.

Now let $r\ge2$ and assume the induction hypothesis for $r-1$.

\begin{lemma*}
  There exist polynomials $U,V\in \ZZ[x]$ such that
  $(1-\omega)^p/(1-\omega^p) = U(\omega)$ and $(1-\omega^p)/(1-\omega)^p =
  V(\omega)$ for all $\omega\in S_q$. (Again, these are units.)
\end{lemma*}

\begin{proof}
  Similarly to the previous lemma, we write $1-\omega^p =
  (1-\omega\zeta_p^0)\dotsm(1-\omega\zeta_p^{p-1})$. The polynomials $U$ and $V$
  are
  \begin{align*}
    U(x) &= \prod_{k=1}^{p-1}\frac{1-x^{(kq/p+1)\ell_k}}{1-x^{kq/p+1}} \\
    V(x) &= \prod_{k=1}^{p-1}\frac{1-x^{kq/p+1}}{1-x}
  \end{align*}
  where $\ell_k$ is a multiplicative inverse of $kq/p+1$ modulo $q$.
\end{proof}

\begin{corollary*}
  If $\omega\in S_q$, then $(1-\omega)^{\phi(q)}/p$ is a unit.
\end{corollary*}

\begin{proof}
  Induct on $r$. For $r=1$, this is the first lemma. For the inductive step,
we are given that $(1-\omega^p)^{\phi(q/p)}/p$ is a unit. By the second lemma,
$(1-\omega)^{\phi(q)}/(1-\omega^p)^{\phi(q/p)}$ is also a unit. Multiplying
these together yields another unit.
\end{proof}

Thus we have polynomials $A, B\in \ZZ[x]$ such that
\begin{align*}
  A(\omega) &= \frac{p}{(1-\omega)^{\phi(q)}}V(\omega)^{z_{q/p}} \\
  B(\omega) &= \frac{(1-\omega)^{\phi(q)}}{p}U(\omega)^{z_{q/p}}
\end{align*}
for all $\omega\in S_q$.

Given $g\in \ZZ[x]$, consider the $p$th roots of unity filter \[S(x) :=
\sum_{k=0}^{p-1} g(\zeta_p^k x) = p\cdot h(x^p),\] where $h\in \ZZ[x]$.
Then \[ph(\eta) = S(\omega) = \sum_{\omega^p = \eta} g(\omega)\] for all $\eta\in
S_{q/p}$, so
\begin{align*}
\frac{h(\eta)}{(1-\eta)^{z_{q/p}}}
= \frac{S(\omega)}{p(1-\eta)^{z_{q/p}}}
&= \sum_{\omega^p = \eta} \frac{(1-\omega)^{pz_{q/p}}}{(1-\omega^p)^{z_{q/p}}} \frac{g(\omega)}{p(1-\omega)^{pz_{q/p}}} \\
&= \sum_{\omega^p = \eta}
U(\omega)^{z_{q/p}}\frac{(1-\omega)^{\phi(q)}}{p}\frac{g(\omega)}{(1-\omega)^{z_q}}.
\end{align*}
(Implicit in the last line is $z_q=\phi(q)+pz_{q/p}$.)
Since $U(\omega)$ and $(1-\omega)^{\phi(q)}/p$ are units, we can let $g=A\cdot
f$ for arbitrary $f\in \ZZ[x]$, so that the expression in the summation
simplifies to $f(\omega)/(1-\omega)^{z_q}$.
From this we conclude that for any $f\in \ZZ[x]$, there exists $h\in
\ZZ[x]$ such that
\begin{align*}
  \sum_{\omega\in S_q}\frac{f(\omega)}{(1-\omega)^{z_q}} &= \sum_{\eta\in
  S_{q/p}}\sum_{\omega^p=\eta}\frac{f(\omega)}{(1-\omega)^{z_q}} \\
                                                         &= \sum_{\eta\in
                                                         S_{q/p}}\frac{h(\eta)}{(1-\eta)^{z_{q/p}}}.
\end{align*}
By the inductive hypothesis, this is always an integer.

In the other direction, for $\eta\in S_{q/p}$ we have
\begin{align*}
  \sum_{\omega^p = \eta} \frac{B(\omega)}{(1-\omega)^{1+z_q}} &=
  \sum_{\omega^p=\eta}\frac{1}{p(1-\omega^p)^{z_{q/p}}(1-\omega)} \\
& = \frac{1}{p(1-\eta)^{z_{q/p}}}\sum_{\omega^p = \eta} \frac{1}{1-\omega} \\
& = \frac{1}{p(1-\eta)^{z_{q/p}}}\left[\frac{px^{p-1}}{x^p - \eta}\right]_{x=1}
\\
& = \frac{1}{(1-\eta)^{1 + z_{q/p}}}.
\end{align*}
Summing over all $\eta\in S_{q/p}$, we conclude by the inductive hypothesis that
\[\sum_{\omega\in S_q}\frac{B(\omega)}{(1-\omega)^{1+z_q}}=\sum_{\eta\in
S_{q/p}}\frac{1}{(1-\eta)^{1+z_{q/p}}}\]
is not an integer. This completes the solution.

\paragraph{Solution 2 (Nikolai Beluhov).} %Newton sums

Suppose that the complex numbers $\frac{1}{1-\omega}$ for $\omega \in S_q$ are
the roots of
\[P(x) = x^d - c_1x^{d - 1} + c_2x^{d - 2} - \dotsb \pm c_d,\]
so that $c_k$ is their $k$-th elementary symmetric polynomial and $d = \phi(q) =
(p - 1)p^{r - 1}$. Additionally denote
\[S_n = \sum_{\omega\in S_q} \frac{1}{(1 - \omega)^n}.\]
Then, by Newton's identities,
\begin{align*}
  S_1 &= c_1, \\
  S_2 &= c_1S_1 - 2c_2, \\
  S_3 &= c_1S_2 - c_2S_1 + 3c_3,
\end{align*}
and so on. The general pattern when $n\leq d$ is
\[S_n = \left[\sum_{j = 1}^{n - 1} (-1)^{j + 1}c_jS_{n - j}\right] + (-1)^{n +
1}nc_n.\]
After that, when $n > d$, the pattern changes to
\[S_n = \sum_{j = 1}^d (-1)^{j + 1}c_jS_{n - j}.\]

\begin{lemma*}
  All of the $c_i$ are integers except for $c_d$. Furthermore, $c_d$ is $1/p$
  times an integer.
\end{lemma*}

\begin{proof}
The $q$th cyclotomic polynomial is
\[\Phi_q(x)=1+x^{p^{r-1}}+x^{2p^{r-1}}+\dotsb+x^{(p-1)p^{r-1}}.\]
The polynomial
\[Q(x) = 1+(1+x)^{p^{r-1}}+(1+x)^{2p^{r-1}}+\dotsb+(1+x)^{(p-1)p^{r-1}}\]
has roots $\omega-1$ for $\omega \in S_q$, so it is equal to $p(-x)^dP(-1/x)$ by
comparing constant coefficients. Comparing the remaining coefficients, we find
that $c_n$ is $1/p$ times the $x^{n}$ coefficient of $Q$.

Since $(x + y)^p \equiv x^p + y^p \pmod{p}$, we conclude that, modulo $p$,
\begin{align*}
  Q(x) &\equiv 1 + \big(1 + x^{p^{r - 1}}\big) + \big(1 + x^{p^{r - 1}}\big)^2 + \dotsb + \big(1 + x^{p^{r -
1}}\big)^{p - 1} \\
       &\equiv \Big[\big(1 + x^{p^{r - 1}}\big)^p - 1\Big]/x^{p^{r - 1}}.
\end{align*}

Since $\binom{p}{j}$ is a multiple of $p$ when $0 < j < p$, it follows that all
coefficients of $Q(x)$ are multiples of $p$ save for the leading one. Therefore,
$c_n$ is an integer when $n < d$, while $c_d$ is $1/p$ times an integer.
\end{proof}

By the recurrences above, $S_n$ is an integer for $n < d$. When $r = 1$, we get
that $dc_d$ is not an integer, so $S_d$ is not an integer, either. Thus the
answer for $r=1$ is $n=p-1$.

Suppose now that $r \ge 2$. Then $dc_d$ does become an integer, so $S_d$ is an integer as well.

%Using our recurrence for the $S_n$ with $n > d$, we see that the smallest $n$
%with $S_n$ non-integer is $d$ larger than the smallest $n$ with $S_n$ not a multiple of $p$.

\begin{lemma*}
  For all $n$ with $1 \le n \le d$, we have $\nu_p(nc_n) \ge r - 2$.
  Furthermore, the smallest $n$ such that $\nu_p(nc_n) = r - 2$ is $d - p^{r - 1} +
  1$.
\end{lemma*}
\begin{proof}
  The value of $nc_n$ is $1/p$ times the coefficient of $x^{n-1}$ in the
  derivative $Q'(x)$. This derivative is
\[p^{r - 1}(1 + x)^{p^{r - 1} - 1}\left[\sum_{k = 1}^{p - 1} k(1 + x)^{(k - 1)p^{r -
1}}\right].\]

What we want to prove reduces to showing that all coefficients of the
polynomial in the square brackets are multiples of $p$ except for the leading one.

Using the same trick $(x + y)^p \equiv x^p + y^p \pmod{p}$ as before and also
writing $w$ for $x^{p^{r - 1}}$, modulo $p$ the polynomial in the square brackets
becomes
\[1 + 2(1 + w) + 3(1 + w)^2 + \dotsb + (p - 1)(1 + w)^{p - 2}.\]
This is the derivative of
\[1 + (1 + w) + (1 + w)^2 + \dotsb + (1 + w)^{p - 1} = [(1 + w)^p - 1]/w\]
and so, since $\binom{p}{j}$ is a multiple of $p$ when $0 < j < p$, we are
done.
\end{proof}

Finally, we finish the problem with the following claim.
\begin{claim*}
  Let $m=d-p^{r-1}$. Then for all $k\geq 0$ and $1\leq j\leq d$, we have
  \begin{align*}
    \nu_p(S_{kd+m+1}) &= r-2-k \\
    \nu_p(S_{kd+m+j}) &\geq r-2-k.
  \end{align*}
\end{claim*}

\begin{proof}
  First, $S_1, S_2, \dots, S_m$ are all divisible by $p^{r - 1}$ by Newton's
  identities and the second lemma. Then $\nu_p(S_{m + 1}) = r - 2$ because
  \[\nu_p((m+1)c_{m+1})=r-2,\]
  and all other terms in the recurrence relation are divisible by $p^{r-1}$. We
  can similarly check that $\nu_p(S_{n})\geq r-2$ for $m+1\leq n \leq d$.
  Newton's identities combined with the first lemma now imply
  the following for $n > d$:
  \begin{itemize}
    \item If $\nu_p(S_{n-j})\geq \ell$ for all $1\leq j\leq d$ and
      $\nu_p(S_{n-d})\geq \ell+1$, then $\nu_p(S_{n})\geq \ell$.
    \item If $\nu_p(S_{n-j})\geq \ell$ for all $1\leq j\leq d$ and
      $\nu_p(S_{n-d})=\ell$, then $\nu_p(S_{n})=\ell-1$.
  \end{itemize}
  Together, these prove the claim by induction.
\end{proof}
By the claim, the smallest $n$ for which $\nu_p(S_n) < 0$ (equivalent to $S_n$
not being an integer, by the recurrences) is
\[n=(r-1)d+m+1=((p-1)r-1)p^{r-1}+1.\]

\begin{remark*}
  The original proposal was the following more general version:
  \begin{quote}
    Let $n$ be an integer with prime power factorization $q_1\dotsm q_m$.
    Let $S_n$ denote the set of primitive $n$th roots of unity. Find all tuples of nonnegative integers $(z_1,\dots,z_m)$ such that
    \[
      \sum_{\omega\in S_n} \frac{f(\omega)}{(1-\omega^{n/q_1})^{z_1}\dotsm (1-\omega^{n/q_m})^{z_m}} \in \ZZ
    \]
    for all polynomials $f\in \ZZ[x]$.
  \end{quote}
  The maximal $z_i$ are exponents in the prime ideal factorization of the \href{https://en.wikipedia.org/wiki/Different_ideal}{different ideal} of the cyclotomic extension $\QQ(\zeta_n)/\QQ$.
\end{remark*}

\begin{remark*}
Let $F = (x^p - 1)/(x-1)$ be the minimal polynomial of $\zeta_p = e^{2\pi i/p}$ over $\QQ$.
A calculation of Euler shows that
\[
(\ZZ[\zeta_p])^*
:= \{\alpha = g(\zeta_p)\in \QQ[\zeta_p]: \sum_{\omega \in S_p}
f(\omega)g(\omega)\in \ZZ\; \forall f\in \ZZ[x]\}
= \frac{1}{F'(\zeta_p)}\cdot \ZZ[\zeta_p],
\]
where
\[
F'(\zeta_p) = \frac{p\zeta_p^{p-1} - [1+\zeta_p+\dotsb+\zeta_p^{p-1}]}{1-\zeta_p} = p(1-\zeta_p)^{-1}\zeta_p^{p-1}
\]
is $(1-\zeta_p)^{[p-1]-1} = (1-\zeta_p)^{p-2}$ times a unit of
$\ZZ[\zeta_p]$. Here, $(\ZZ[\zeta_p])^*$ is the dual lattice of
$\ZZ[\zeta_p]$.
\end{remark*}

%\begin{remark*}
%Let $\alpha$ be algebraic of degree $d$ over $\QQ$, and let $f\in \QQ[x]$ be the minimal polynomial of $\alpha$ (of degree $d$).
%Hidden in the previous remark is Euler's calculation: the trace of $\alpha^i/f'(\alpha)$ (sum over conjugates) is $0$ for $i=0,1,\dots,d-2$ and $1$ for $i=d-1$, proven either using partial fractions, Lagrange interpolation, or other symmetric sum techniques (e.g. Newton sums).
%All of this can be phrased more directly (e.g. in terms of symmetric sums of $S_n$), so one could likely use standard elementary methods to directly compute the sums in the problem statement.
%\end{remark*}

\begin{remark*}
Let $K = \QQ(\omega)$, so $(p)$ factors as $(1-\omega)^{p-1}$ in the ring of integers $\mathcal{O}_K$ (which, for cyclotomic fields, can be shown to be $\ZZ[\omega]$).
%total ramification
In particular, the \emph{ramification index} $e$ of $(1-\omega)$ over $p$ is the exponent, $p-1$.
Since $e = p-1$ is not divisible by $p$, we have so-called \emph{tame ramification}.
%So look at the exponent of $1-\omega$ in the inverse different, get $[p-1]-1 = p-2$.
Now by the
\href{https://en.wikipedia.org/wiki/Different_ideal\#Ramification}{ramification
theory} of Dedekind's different ideal, the exponent $z_1$ that works when $n=p$ is $e-1 = p-2$.

Higher prime powers are more interesting because of wild ramification: $p$ divides $\phi(p^r) = p^{r-1}(p-1)$ if and only if $r>1$.
(This is a similar phenomena to how Hensel's lemma for $x^2 - c$ is more interesting mod powers of 2 than mod odd prime powers.)
\end{remark*}

\begin{remark*}
Let $F = (x^q - 1)/(x^{q/p}-1)$ be the minimal polynomial of $\zeta_q = e^{2\pi i/q}$ over $\QQ$.
The aforementioned calculation of Euler shows that
\[
(\ZZ[\zeta_q])^*
:= \{\alpha = g(\zeta_q)\in \QQ[\zeta_q]: \sum_{\omega \in S_q}
f(\omega)g(\omega)\in \ZZ \; \forall f\in \ZZ[x]\}
= \frac{1}{F'(\zeta_q)}\cdot \ZZ[\zeta_q],
\]
where the chain rule implies (using the computation from the prime case)
\[
F'(\zeta_q) = [p(1-\zeta_p)^{-1}\zeta_p^{p-1}]\cdot \frac{q}{p}\zeta_q^{(q/p) - 1} = q(1-\zeta_p)^{-1}\zeta_q^{-1}.
\]
is $(1-\zeta_q)^{r\phi(q) - q/p} = (1-\zeta_q)^{z_q}$ times a unit of $\ZZ[\zeta_q]$.
\end{remark*}