help $ $ $ $

I guessed that it was $p-1$, but I have no idea.

I tried writing out the polynomial which has roots 1/(1-zeta^k) and then using Newton sums and vp’s, but couldn’t figure it out fully

the answer is q*r*(p-1/p)-(q/p)+1

Mop2018 wrote: the answer is q*r*(p-1/p)-(q/p)+1 Ahh yes this is so obvious, isn't it

Mop2018 wrote: the answer is q*r*(p-1/p)-(q/p)+1 This is correct, and for the record it's been checked for $q = 2, 4, 8, 16, 32, 64, 128, 3, 9, 27, 81, 5, 25$ and is easily proven true for $r = 1$. Looking forward to seeing the solution . (Some might write it as $r(p^r-p^{r-1}) - (p^{r-1}-1)$)

Good day sirs. This solution was communicated to me by the critics of the Moratorium On Solving Problems. Note that $\zeta^k$ for $k$ relatively prime to $p$ is a root to the polynomial $x^{(p-1)p^{r-1}}+x^{(p-2)p^{r-1}}+\cdots +1$. Also, note that if we let $y_k=\frac{1}{1-\zeta^k}$, then $\zeta^k=\frac{y_k-1}{y_k}$. Therefore, $y_k$ for $1\leq k\leq p^r$ relatively prime to $p$ form the set of roots of the polynomial $$pQ(y)=(y-1)^{(p-1)p^{r-1}}+(y-1)^{(p-2)p^{r-1}}y^{p^{r-1}}+\cdots+y^{(p-1)p^{r-1}}.$$ The magnitude of the coefficient of $y^{(p-1)p^{r-1}-i}$ is $${(p-1)p^{r-1}\choose i}+{(p-2)p^{r-1}\choose i}+\cdots+{p^{r-1}\choose i}+{0\choose i}.$$ We claim that these coefficients are all divisible by $p$ except for when $i=(p-1)p^{r-1}$. Note that if $v_p(i)<r-1$, this is true by Kummer's Theorem. When $v_p(i)=r-1$, we let $i=i'p^{r-1}$. Then, we use Lucas' Theorem to find $${(p-1)p^{r-1}\choose i}+{(p-2)p^{r-1}\choose i}+\cdots+{p^{r-1}\choose i}+{0\choose i}\equiv {p-1\choose i'}+{p-2\choose i'}+\cdots+{0\choose i'}\equiv {p\choose i'+1} (\text{mod } p).$$Note that ${p\choose i'+1}$ is not divisible by $p$ only when $i'=p-1$, or $i=(p-1)p^{r-1}$, so our claim is proven. Next, we claim that $v_p\left(i\left({(p-1)p^{r-1}\choose i}+{(p-2)p^{r-1}\choose i}+\cdots+{p^{r-1}\choose i}+{0\choose i}\right)\right)\geq r$ for $i\leq (p-2)p^{r-1}$ and $v_p\left(i\left({(p-1)p^{r-1}\choose i}+{(p-2)p^{r-1}\choose i}+\cdots+{p^{r-1}\choose i}+{0\choose i}\right)\right)=r-1$ otherwise. Note that $$i\left({(p-1)p^{r-1}\choose i}+{(p-2)p^{r-1}\choose i}+\cdots+{p^{r-1}\choose i}+{0\choose i}\right)=p^{r-1}\left((p-1){(p-1)p^{r-1}-1\choose i-1}+(p-2){(p-2)p^{r-1}-1\choose i-1}+\cdots\right).$$It remains to determine when $p$ divides $\left((p-1){(p-1)p^{r-1}-1\choose i-1}+(p-2){(p-2)p^{r-1}-1\choose i-1}+\cdots\right)$. We do this using Lucas' Theorem. Note that the last $r-1$ digits of $mp^{r-1}-1$ for $0\leq m\leq p-1$ are all $p-1$ base $p$. In otherwords, these last digits will not result in anything divisible by $p$, and is something held in common. We can divide out by this factor and let $i'$ be the $r$th place digit of $i-1$ to obtain $$(p-1){p-2\choose i'}+(p-2){p-3\choose i'}+\cdots=(i'+1)\left({p-1\choose i'+1}+{p-2\choose i'+1}+\cdots\right)=(i'+1){p\choose i'+2}.$$This is divisible by $p$ when $i'<p-2$, and otherwise not (provided $i$ is in the range $[1, (p-1)p^{r-1}]$. From here, we can see that our claim is true. Now, let $S_n$ denote the sum mentioned in the problem, and let $\sigma_i$ denote the elementary symmetric sums for the $y_k$. Then, $Q(y)=y^{(p-1)p^{r-1}}-\sigma_1y^{(p-1)p^{r-1}}+\sigma_2y^{(p-1)p^{r-1}-2}-\cdots$. We have proven that $\sigma_i$ is an integer for all $i$ except $i=(p-1)p^{r-1}$. We have set everything up for the perfect induction. The basic idea is that $S_n=\sigma_1S_{n-1}-\sigma_2S_{n-2}+\cdots+(-1)^{n-2}\sigma_{n-1}S_{1}+(-1)^{n-1}n\sigma_n$ by Newton Sums for $1\leq n\leq (p-1)p^{r-1}$. Furthermore, we have $S_n=\sigma_1S_{n-1}-\sigma_2S_{n-2}+\cdots+(-1)^{(p-1)p^{r-1}}\sigma_{(p-1)p^{r-1}}S_{n-(p-1)p^{r-1}}$ for larger $n$. The first equation sets up our "initial" conditions on $v_p(S_n)$ and the latter provides us with a way to extend them (emphasis on $\sigma_{(p-1)p^{r-1}}=\pm \frac{1}{p}$, which decreases the $v_p$). The details that finish this solution are left as an exercise for the reader.

Solved with rama1728. Answer: $\boxed{n = rp^r - rp^{r-1} - p^{r-1} + 1}.$ The set of $\zeta^k$ are the roots of the polynomial $x^{(p-1)p^{r-1}}+x^{(p-2)p^{r-1}}+\cdots +1$. Note $a_k = \frac{1}{1-\zeta^k} \iff \zeta^k=\frac{a_k-1}{a_k}.$ So the $a_k$ are the roots to the monic polynomial $$P(x)=\frac{1}{p} \left( (x-1)^{(p-1)p^{r-1}}+(x-1)^{(p-2)p^{r-1}}x^{p^{r-1}}+\cdots+x^{(p-1)p^{r-1}} \right).$$We want to find the minimum $n$ where $v_p(S_n) < 0,$ where $S_n$ is the $n$th Newton sum. We can ignore any $q \ne p;$ the $v_q$ of all the coefficients of $P(x)$ is nonnegative. For any $1 \le i \le (p-1)p^{r-1},$ the $i$th symmetric sum, denoted $\sigma_i,$ is $$\frac{1}{p} \left({(p-1)p^{r-1}\choose i}+{(p-2)p^{r-1}\choose i}+\cdots+{0\choose i} \right)$$by Vieta's. If $v_p(i) < r-1$ then Lucas's Theorem implies each term in the inner sum $\equiv 0 \pmod{p},$ so then $v_p(\sigma_i) \ge 0.$ If $v_p = r-1$ then Lucas implies the inner sum is $\equiv 0 \pmod{p}$ iff $$0 \equiv {p-1\choose i_1}+{p-2 \choose i_1}+\cdots+{0\choose i_1} = \binom{p}{i_1+1} \pmod{p},$$where $i_1$ is the $p^{r-1}$ digit of $i.$ This occurs iff $i_1 \ne p-1.$ Thus, $v_p(\sigma_i) \ge 0$ iff $i \ne (p-1)p^{r-1},$ otherwise $v_p(\sigma_i) = -1.$ Also, \begin{align*} \sigma_i \times i &= \frac{1}{p} \left(i{(p-1)p^{r-1}\choose i}+i{(p-2)p^{r-1}\choose i}+\cdots+i{0\choose i} \right) \\ &= p^{r-2} \left((p-1){(p-1)p^{r-1}-1\choose i-1}+(p-2){(p-2)p^{r-1}-1\choose i-1}+\cdots \right). \\ \end{align*}Let $i_1$ be the $p^{r-1}$ digit of $i-1.$ By Lucas, the inner sum is $0 \pmod{p}$ iff $$0 \equiv (p-1){p-2\choose i_1}+(p-2){p-3\choose i_1}+ \cdots = (i_1+1) \left({p-1\choose i_1+1}+{p-2\choose i_1+1}+\cdots \right) = (i_1+1) \binom{p}{i_1+2} \pmod{p}.$$This is $0 \pmod{p} \iff i' \ne p-2 \iff i \le (p-2)p^{r-1}.$ So for $i\le (p-2)p^{r-1},$ then $v_p(\sigma_i \times i) \ge r-1$ and if $i >(p-2)p^{r-1}$ then $v_p(\sigma_i \times i) = r-2.$ Note $$S_n =\sigma_1 \times S_{n-1} - \sigma_{2} \times S_{n-2} + \dots - (-1)^n \times n \times \sigma_n.$$for $n \le (p-1)p^{r-1}.$ Note that all the $\sigma_i$ are integers except for $\sigma_{(p-1)p^{r-1}},$ which has $v_p$ of $-1.$ We verify by a quick induction that $v_p(S_n) \ge r-1$ for all $1 \le n \le (p-2)p^{r-1},$ since $v_p(n \times \sigma_n) \ge r-1.$ For $n = (p-2)p^{r-1}+1,$ all terms on the RHS have $v_p \ge r-1$ except for the last, which has $v_p$ of $r-2$ exactly since $v_p(n \times \sigma_n) = r-2.$ So $v_p(S_n) =r-2$ here. When $(p-2)p^{r-1}+1\le n \le (p-1)p^{r-1},$ we verify by a quick induction that all terms on the RHS have $v_p \ge r-2.$ So $v_p(S_n) \ge r-2$ here. We claim for all nonnegative integers $l,$ all $n$ in $[(p-2)p^{r-1}+1+l(p-1)p^{r-1}, (p-2)p^{r-1}+(l+1)(p-1)p^{r-1}]$ obey $v_p(S_n) \ge r-2-l,$ and in particular, if $n = (p-2)p^{r-1}+1+l(p-1)p^{r-1}$ then $v_p(S_n) = r-2-l$ exactly. We prove with induction, with base case already done. If it is true for $l-1$ where $l-1 \ge 0,$ take $n$ in $[(p-2)p^{r-1}+1+l(p-1)p^{r-1}, (p-2)p^{r-1}+(l+1)(p-1)p^{r-1}].$ So $n$ obeys the recurrence $$S_n =\sigma_1 \times S_{n-1} - \sigma_2 \times S_{n-2} + \dots - (-1)^{(p-1)p^{r-1}} \times \sigma_{(p-1)p^{r-1}} \times S_{n-(p-1)p^{r-1}}.$$We make the inductive step as follows: if $n =(p-2)p^{r-1}+1+l(p-1)p^{r-1}$ specifically, then all terms on the RHS have $v_p \ge r-1-l$ except for the last, which has $v_p$ of $r-2-l$ exactly (by the inductive hypothesis and the fact that $v_p(\sigma_{(p-1)p^{r-1}}) = -1$). So $v_p(S_n) = r-2-l$ here. For the other $n$ in the interval, we verify by a (separate) quick induction that all terms on the RHS have $v_p \ge r-2-l.$ So $v_p(S_n) \ge r-2-l$ here. Setting $l = r-1$ in $(p-2)p^{r-1}+1+l(p-1)p^{r-1},$ the desired $n$ simplifies to $rp^r - rp^{r-1} - p^{r-1} + 1.$ $\blacksquare$

We can guess the smallest n like this: Let S(n) be the sum, it is easy to see that the smallest n is not less than p^(r-1)*(p-1), after using newton's sum, we might guess that vp(S(n))=vp(S(n-p^(r-1)*(p-1)))-1=vp(S(n-2*p^(r-1)*(p-1)))-2=..., therefore we look at the vp's of S(0),S(1),...,S(p^(r-1)*(p-1)-1), and assume the smallest value of the vp's is j, let i be the smallest integer such that vp(S(i))=j, then the answer will be i+(j+1)(p^(r-1)*(p-1)). Using newton's sum again and trying several cases, we conclude that j=r-2 when r>=2 and finally, prove that our guesses are right. This is a very nice and hard NT problem.

This problem was proposed by Victor Wang. I'll show the author's solution for this problem since it has nice number theoretic ideas that aren't covered by the other solutions. Let $S_q$ denote the set of primitive $q$th roots of unity (thus, the sum in question is a sum over $S_q$). 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 \mathbb{Z}\]for all $n < n_0$ and $f\in \mathbb{Z}[x]$, whereas for $n=n_0$ there is some $f\in \mathbb{Z}[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$. Lemma. There exist polynomials $u,v\in \mathbb{Z}[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 unit (invertible algebraic integer), namely $v(\omega)$.) Proof. Note that $p = (1-\omega)\cdots(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$. Now, the main idea: given $g\in \mathbb{Z}[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)\cdots(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 \[ \mathbb{Z} \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\mathbb{Z},\]so the sum is not an integer for $n=p-1$. Now let $r\ge2$ and assume the induction hypothesis for $r-1$. Lemma. There exist polynomials $U,V\in \mathbb{Z}[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.) Proof. Similarly to the previous lemma, we write $1-\omega^p = (1-\omega\zeta_p^0)\cdots(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$. Corollary. If $\omega\in S_q$, then $(1-\omega)^{\phi(q)}/p$ is a unit. 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. Thus we have polynomials $A, B\in \mathbb{Z}[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 \mathbb{Z}[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 \mathbb{Z}[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 \mathbb{Z}[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 \mathbb{Z}[x]$, there exists $h\in \mathbb{Z}[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.

New to LaTeX on aops. The minimum $n$ is $1 + p^{r-1}((p-1)r-1)$. For brevity let $d = (p-1)p^{r-1}$. The polynomial with roots $\zeta_k$ with $\gcd(k,p)=1$ is $$\Phi_{q}(x) = \frac{x^{p^r}-1}{x^{p^{r-1}} - 1} = 1 + x^{p^{r-1}} + x^{2p^{r-1}} + \cdots + x^{(p-1)p^{r-1}}.$$Then define $$Q(x) = x^{q}\Phi_{q}\left(1-\frac{1}{x}\right) = (x-1)^{(p-1)p^{r-1}} + x^{p^{r-1}}(x-1)^{(p-2)p^{r-1}} + \cdots + x^{(p-1)p^{r-1}},$$which has the $d$ roots $\frac{1}{1-\zeta_k}$. The problem deals with $Q$'s power sums, which we call $S_n$. Rearranging $Q(x)$, we can isolate the $x^d$ term on one side:\begin{align*} x^{d} &= \frac{px^d-Q(x)}{p} = -\frac{1}{p} + c_1x + c_2x^2 + c_3x^3 + \ldots + c_{d-1}x^{d-1}. \end{align*}By Newton's recurrences on power sums, this implies $$S_n = -\frac{1}{p}S_{n-d} + c_1S_{n-d+1} + c_2S_{n-d+2} + \cdots + c_{d-1}S_{n-1}.$$ Claim -- The $c_1,c_2,\ldots,c_{d-1}$ are integers. Proof: The $x^{d-k}$th coefficient of $Q(x)$ is \begin{align*} &(-1)^{k}\left( \binom{(p-1)p^{r-1}}{k} + \binom{(p-2)p^{r-1}}{k} + \cdots + \binom{0}{k} \right) \end{align*}which by Lucas theorem is a multiple of $p$ if $k\neq 0\pmod{p^{r-1}}$. Otherwise, $k = p^{r-1}k'$ for a $k' < p-1$, by Lucas again, becomes \begin{align*} \binom{p-1}{k'} + \binom{p-2}{k'} + \cdots + \binom{k'}{k'} \equiv \binom{p}{k'+1} \equiv 0 \pmod{p}. \end{align*}by the hockey stick identity. When we divide $Q(x)$ by $p$, the $c_1,\ldots,c_{d-1}$ are integers. $\hfill\clubsuit$ Now we have a tool to generate power sums, provided we already have $d$ terms. Since the only term of the Newton's recurrence that is noninteger is the last, $\frac{1}{p}$, $p$ is the only prime for which $v_p$ of $S_n$ may go negative. To this end, we compute $v_p(S)$ Claim -- (Calculation on negative $n$) The $n\in\{-d+1, \ldots, -p^{r-1}\}$, have the property that $v_p(S_n) \geqslant r$, and the $n\in\{-p^{r-1}+1, \ldots, 0\}$, have the property that $v_p(S_n) = r-1$. Proof: Expand $(1-\zeta_k)^{-n}$ by the binomial theorem and group terms raised to the same power. On each exponent $e$, the coefficient is \begin{align*} (-1)^e\binom{n}{e}\times\begin{cases} d & \text{if } v_p(e) = r, \text{ equivalent to } n=0 \\ -\frac{d}{p-1} & \text{if } v_p(e) = r-1 \\ 0 & \text{ otherwise} \end{cases} \end{align*}The first two cases are equivalent modulo $p^r$, hence view them as one. Fix $n$ to the range $ap^{r-1}$ to $(a+1)p^{r-1}-1$. By the Lucas theorem, $\binom{n}{bp^{r-1}} \equiv \binom{a}{b}\pmod{p}$, so $$S_n \equiv (p-1)p^{r-1}\left(\binom{a}{0} - \binom{a}{1} + \binom{a}{2} - \cdots \pm \binom{a}{a} \right) \pmod{p^r}$$The alternating sum of binomial coefficients is usually $0$, but it is $1$ when $a=0$. $\hfill\clubsuit$ Claim -- When $n=dt-p^{r-1}+1$, we have $v_p(S_n) = r-1-t$, the minimum over all smaller $-d<n'<n$. Proof: More or less induction, $t=0$ proved by the previous claim. Only the last term of our recurrence allows us to decrease $v_p(S_n)$. Thus we have $v_p(S_n) \geqslant v_p(S_{n-d}) - 1$ which proves that the next possible smallest value is the $n+d$. This indeed lowers the $v_p$ by $1$, since the sum contains only one term of minimal $v_p$. $\hfill\clubsuit$ So the first non-integer sum occurs when $v_p = -1$, which is $t = r$. It follows that $n=1 + p^{r-1}((p-1)r-1)$, done.

The answer is $\boxed{n=(p-2)p^{r-1}+1+(r-1)(p-1)p^{r-1}}$. Since 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 $\tfrac{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)^ix^{(p-1)p^{r-1}-i}.$$Note that the $x^{(p-1)p^{r-1}}$ coefficient is $p$. For $1 \leq k \leq (p-1)p^{r-1}$, define $$T_k=\sum_{i=1}^{p-1} \binom{ip^{r-1}}{k},$$so the $k$-th symmetric sum of the $\tfrac{1}{1-\zeta^k}$ is $\tfrac{1}{p}T_k$. We now introduce the following key claim. 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$. Proof: 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 $\tbinom{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 \tbinom{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$. $\blacksquare$ 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}$. We are interested in the power sums of the $\tfrac{1}{1-\zeta^k}$. To that end, we will employ Newton's Identities in the following form. Fact: Let $S_i$ denote the $i$-th power sum of the $\tfrac{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_jS_{i-j}\right)+\frac{(-1)^{j+1}}{p}iT_i,$$and for $i>(p-1)p^{r-1}$ we have $$S_i=\sum_{j=1}^k \frac{1}{(-1)^{j+1}}\sigma_jS_{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$. 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}$. 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+{\color{red}0(p-1)p^{r-1}} \leq i \leq (p-2)p^{r-1}+{\color{red}1(p-1)p^{r-1}}$, $\nu_p(S_i)={\color{blue}r-3}$ when $i=(p-2)p^{r-1}+1+{\color{red}1(p-1)p^{r-1}}$, since we know ${\color{blue}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}})={\color{blue}r-2}$. $p^{r-3}$ divides $S_i$ for $(p-2)p^{r-1}+1+{\color{red}1(p-1)p^{r-1}} \leq i \leq (p-2)p^{r-1}+{\color{red}2(p-1)p^{r-1}}$, $\nu_p(S_i)={\color{blue}r-4}$ when $i=(p-2)p^{r-1}+1+{\color{red}2(p-1)p^{r-1}}$, since we know ${\color{blue}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}})={\color{blue}r-3}$. $p^{r-4}$ divides $S_i$ for $(p-2)p^{r-1}+1+{\color{red}2(p-1)p^{r-1}} \leq i \leq (p-2)p^{r-1}+{\color{red}3(p-1)p^{r-1}}$, $\nu_p(S_i)={\color{blue}r-5}$ when $i=(p-2)p^{r-1}+1+{\color{red}3(p-1)p^{r-1}}$, since we know ${\color{blue}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}})={\color{blue}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. $\blacksquare$

Combo The answer is $p^{r-1}(p-2)+1+p^{r-1}(p-1)(r-1)$. The numbers $\frac{1}{1-\zeta^k}$ are roots of $\sum_{j=0}^{p-1}\left(\frac{x-1}{x}\right)^{p^{r-1}\cdot j}$, so they are roots of $\sum_{j=0}^{p-1}(x-1)^{p^{r-1}\cdot j}x^{p^{r-1}(p-1-j)}$. The leading coefficient is $p$ and the ending coefficient is $\pm 1$. The $x^{p^r(p-1)-n}$ coefficient is $\pm \sum_{k=0}^{p-1} \binom{p^{r-1}\cdot k}{n}$, we can show that the $\nu_p$ of this is at least $r-\nu_p(n)$ if $n\le p^r(p-2)$ and is exactly $r-1-\nu_p(n)$ if $n=p^r(p-2)+1$. $\binom{p^{r-1}\cdot k}{n}$ is the number of ways to choose $n$ items out of $p^{r-1}\cdot k$ items, and we can arrange the $p^{r-1}\cdot k$ items in $k$ circles of $p^{r-1}$ items. Then for each way to choose $n$ items, group it with the configurations where each of the circles is rotated in some way (not necessarily all the same way, or rotated at all). There must be a circle with $x$ items selected where $\nu_p(x)\le \nu_p(n)$, so in each group there is a multiple of $p^{r-1-\nu_p(n)}$ configurations by rotating that circle. The amount of groups which don't have a multiple of $p^{r-\nu_p(n)}$ configurations are those with $1$ group that has $n\bmod p^{r-1}$ items, where the items chosen are periodic $\bmod p^{r-1-\nu_p(n)}$, and all other groups having either $0$ or $p^{r-1}$ elements chosen. Thus $\binom{p^{r-1}\cdot k}{n}\equiv \binom{k}{\lfloor n/p^{r-1}\rfloor}\cdot (k-\lfloor n/p^{r-1}\rfloor-1)\cdot \binom{p^{r-1}/p^{\nu_p(n)}}{(n\bmod p^{r-1})/p^{\nu_p(n)}}\bmod p^{r-\nu_p(n)}$ if $p^{r-1}\nmid n$ and $\binom{p^{r-1}\cdot k}{n}\equiv \binom{k}{n/p^{r-1}}\mod p$ if $p^{r-1}\mid n$. Suppose $p^{r-1}\nmid n$. $\binom{p^{r-1}/p^{\nu_p(n)}}{(n\bmod p^{r-1})/p^{\nu_p(n)}}\equiv 0\bmod p^{r-1-\nu_p(n)}$ by Kummer's theorem or repeating the above argument again, so if $j=\lfloor n/p^{r-1}\rfloor$, we can show $\sum_{k=0}^{p-1}\binom{k}{j}(k-j-1)$ is $0\bmod p$ for $j<p-2$ and not $0\bmod p$ for $j=p-2$. For $j=0$, the result is clear. For $j>0$, $\sum_{k=0}^{p-1}\binom{k}{j}(k-j-1)=(j+1)\sum_{k=0}^{p-1}\binom{k+1}{j+1}-(j+2)\sum_{k=0}^{p-1}\binom{k}{j}$=$(j+1)\binom{p+1}{j+2}-(j+2)\binom{p}{j+1}\equiv (j+1)\binom{p+1}{j+2}\bmod p$, this is not $0\bmod p$ only when $j=p-2$. If $p^{r-1}\mid n$, $\sum_{k=0}^{p-1}\binom{k}{n/p^{r-1}}=\binom{p}{n/p^{r-1}+1}\equiv 0\bmod p$ if $n\le p^{r-1}(p-2)$. Let $e_n$ and $p_n$ be the $n$-th symmetric power and sum of $n$-th powers of the roots respectively. $e_n$ is the $x^{p^{r-1}(p-1)-n}$ coefficient times $\frac{1}{p}$ or $-\frac{1}{p}$. Then by induction, we can show $p^{r-1}\mid p_n$ for $n\le p^{r-1}(p-2)$ and $p^{r-2}\mid p_n$ for $p^{r-1}(p-2)<n\le p^{r-1}(p-1)$, with $\nu_p(p_{n})=r-2$ for $n=p^{r-1}(p-2)+1$. This fact is true for $n=1$. For $n\le p^{r-1}(p-2)$, $ne_n$ and $p_1,\dots ,p_{n-1}$ are all divisible by $p^{r-1}$, so by Newton's sums $p_n$ is divisible by $p^{r-1}$. For $n=p^{r-1}(p-2)+1$, $p_1,\dots ,p_{n-1}$ are all divisible by $p^{r-1}$ but $\nu_p(ne_n)=r-2$, so $\nu_p(p_n)=r-2$. For $n>p^{r-1}(p-2)+1$, $ne_n, p_1,\dots ,p_{n-1}$ are all divisible by $p^{r-2}$, so $p^{r-2}\mid p_n$. For $r>1$, $p_n$ is an integer for all $n\le p^{r-1}(p-1)$ since all the summands in the Newton sums are integers, because the only $e_i$ that is not an integer is $e_{p^{r-1}(p-1)}=\frac{1}{p}$, but the only summand it is in is $p^{r-1}(p-1)e_i$. For $r=1$, $p_{p-1}$ is not an integer because $\nu_p(p_{p-1})=-1$ and for $n<p-1$, $p_n$ is an integer. For $n>p^{r-1}(p-1)$, $p_n=e_1p_{n-1}-e_2p_{n-2}+\cdots \pm \frac{1}{p}p_{n-p^{r-1}(p-1)}$. Thus $p_n$ not being an integer is equivalent to $\nu_p(p_n)<0$. Thus for $p^{r-1}(p-1)<n\le p^{r-1}(p-1)+p^{r-1}(p-2)$, $\nu_p(p_n)\ge r-2$, and $\nu_p(p_n)=r-3$ for $n=p^{r-1}(p-1)+p^{r-1}(p-2)+1$. By induction, we can show $\nu_p(p_n)\ge r-k-1$ for $kp^{r-1}(p-1)+p^{r-1}(p-2)$ and $\nu_p(p_n)=r-k-2$ for $n=kp^{r-1}(p-1)+p^{r-1}(p-2)+1$. Thus the answer is $p^{r-1}(p-1)(r-1)+p^{r-1}(p-2)+1$.

700th post! I saw this problem about 9 months ago, and have no idea at all. Now I finally have enough ability to solve, honestly it is just large amount of calculation. Let $T:=\{\zeta^k:\gcd(k,p)=1\},$ then $|T|=p^{r-1}(p-1)$ Note that Cyclotomic Polynomial $$\Phi_{p^r}(x)=\frac{x^{p^r}-1}{\Phi_{p^{r-1}}(x)\cdots \Phi_{{p}}(x)}=\frac{x^{p^r}-1}{x^{p^{r-1}}-1}=x^{p^{r-1}(p-1)}+\cdots +x^{p^{r-1}}+1.$$Define $\sigma_i$ be the denote the elementary symmetric sums for $\frac{1}{1-\zeta}$ and $S_i$ be the Newton Sum. Since $$\begin{aligned} \prod_{\zeta\in T}\left(x-\frac 1{1-\zeta}\right) &=\prod_{\zeta\in T}\frac x{1-\zeta}\left(1-\frac 1x-\zeta\right) \\&=\frac{x^{p^{r-1}(p-1)}\Phi_{p^r}\left(1-\frac 1x\right)}{\Phi_{p^r}(1)} \\&=\frac 1p{x^{p^{r-1}(p-1)}}\sum_{t=0}^{p-1}\left(1-\frac 1x\right)^{p^{r-1}t} \\&=\frac 1p{x^{p^{r-1}(p-1)}}\sum_{t=0}^{p-1}\sum_{j=0}^{p^{r-1}(p-1)}\binom{p^{r-1}t}j\left(-\frac 1x\right) ^j \\&=\frac 1p\sum_{j=0}^{p^{r-1}(p-1)}\left[(-1)^j\sum_{t=0}^{p-1}\binom{p^{r-1}t}j\right]x^{p^{r-1}(p-1)-j} \\&=\sum_{j=0}^{p^{r-1}(p-1)}(-1)^j\sigma_jx^{p^{r-1}(p-1)-j}. \end{aligned}$$Therefore for all $0\le j\le p^{r-1}(p-1),$ $$\sigma_j=\frac 1p\sum_{t=0}^{p-1}\binom{p^{r-1}t}j.$$We first prove that $\sigma_j$ is not an integer iff $j=p^{r-1}(p-1),$ by Lucas Theorem $p\mid \sum_{t=0}^{p-1}\binom{p^{r-1}t}j$ when $p^{r-1}\nmid j.$ When $p^{r-1}\mid j,$ say $j=p^{r-1}j',$ by Lucas Theorem $$\sum_{t=0}^{p-1}\binom{p^{r-1}t}j\equiv \binom{0}0^{r-1}\sum_{t=0}^{p-1}\binom{t}{j'}\equiv \binom{p}{j'+1}\pmod p.$$Which is not multiple of $p$ iff $j=p-1,$ $j=p^{r-1}(p-1).$ Now we calculate Newton's Sum. When $r=1$ obviously the answer is $p-1,$ now let $r\ge 2.$ First for all $k\le p^{r-1}(p-1),$ $$S_k=k(-1)^{k+1}\sigma_k+\sum_{i=1}^{k-1}(-1)^{i+1}\sigma_iS_{k-i}.$$Since $\sigma_1,\ldots ,\sigma_{p^{r-1}(p-1)-1}$ are all integer, apparently by induction we can show $S_1,\ldots ,S_{p^{r-1}(p-1)-1}$ are all integer. Note that $p^{r-1}(p-1)(-1)^{k+1}\sigma_{p^{r-1}(p-1)}\in\mathbb Z,$ this gives $S_{p^{r-1}(p-1)}\in\mathbb Z.$ For all $k>p^{r-1}(p-1),$ $$\sum_{i=0}^{p^{r-1}(p-1)}\sigma_iS_{k-i}=0.$$Since $\sigma_1,\ldots ,\sigma_{p^{r-1}(p-1)-1}$ are all integer, if $n_0$ is the minimum integer s.t. $S_{n_0}\notin\mathbb Z,$ then $n_1:=n_0-p^{r-1}(p-1)$ is the minimum integer s.t. $S_{n_1}\notin p\mathbb Z,$ define $n_2,\ldots$ in this way. Now let $n_0=kp^{r-1}(p-1)+m$ where $k,m\in\mathbb N$ and $m<p^{r-1}(p-1).$ Then $n_k=n_0-kp^{r-1}(p-1)$ is the minimum integer s.t. $S_{n_k}\notin p^k\mathbb Z.$ Now we only need to calculate $\nu_p(S_k)$ where $k\le p^{r-1}(p-1).$ In fact by Newton's Sum straightforward induction shows for $1 \le i \le (p-2)p^{r-1}$, $S_i\in p^{r-1}\mathbb Z$, but $\nu_p(S_{(p-2)p^{r-1}+1})=r-2$. Then induct again shows that for $(p-2)p^{r-1} \leq i \leq (p-1)p^{r-1}$, $S_i\in p^{r-2}\mathbb Z$. Therefore $n_k=p^{r-1}(p-2)+1,$ so $$n_0=\boxed{(r-1)p^{r-1}(r-1)+p^{r-1}(r-2)+1}$$as desired.$\Box$