Fiddled around with primitive roots and group theory and got nothing (except trivial progress of $k=1$ and $k=m$), any solution?

I inducted, but I'm not gonna say I'm right until someone better than me posts something.

brainiac1 wrote: I inducted, but I'm not gonna say I'm right until someone better than me posts something. That actually works? I tried this for 2 mins and just decided to work on #2 for the rest of the time.

@2above me_irl

I tried strong induction on N where you divide out the largest prime factor each time but didn't finish.

brainiac1 wrote: I inducted, but I'm not gonna say I'm right until someone better than me posts something. How... I tried to prove the $k=2$ case for two hours and got nothing...

Shaddoll wrote: I tried strong induction on N where you divide out the largest prime factor each time but didn't finish. I think this works if $n$ is squarefree. Then induct again to cover all the other cases.

This was all I could prove... Does that get 1 point?

not true for n=42 (consider p=2, you get 8 a's 1 mod 4 and 4 a's 3 mod 4)

I just realized I called primitive roots generators mod $p$. I mean it's technically true but still O_O.

r3mark wrote: not true for n=42 (consider p=2, you get 8 a's 1 mod 4 and 4 a's 3 mod 4) RIP 0 for me!

I mentioned cyclotomic polynomials and proved that $(x-a_1)(x-a_2)...(x-a_m) \equiv x^m \pm 1$ mod $n$, would that get a point? $k$ odd was easy because you can just pair up terms, but couldn't make much progress on $k$ even

Ok, time to reveal more details of my solution. I didn't induct on $k$, I inducted on $n$. >hoping it's still correct so far. >lowkey gonna reveal my solution one sentence at a time.

Ok, 1 more detail of my solution. The case when $n=2$ is trivial. EDIT: Someone just provide a solution before I die of a heart attack as a teenager.

Shaddoll wrote: I tried strong induction on N where you divide out the largest prime factor each time but didn't finish. This should work, but the proof is different depending on whether or not the largest prime factor $p$ of $n$ divides $\frac{n}{p}$. If not, I had to use the fact that \[ p-1 \mid (k+1)! \cdot (1^k+2^k+\cdots+(p-1)^k) \]for all $k$.

I thought initially this was medium-hard, but woww it takes forever to write up. It took me over an hour to put all of this together. For brevity, given any $n$, we let $A(n) = \left\{ 1 \le x \le n, \gcd(x,n) = 1 \right\}$ (thus $\# A(n) = \varphi(n)$). Also, let $S(n,k) = \sum_{a \in A(n)} a^k$. We will prove the stronger statement (which eliminates the hypothesis on $n$). Claim: Let $n \ge 2$ be arbitrary (and $k \in {\mathbb Z}$). If $p \mid n$, then \[ \nu_p (\varphi(n)) \le \nu_p(S(n,k)). \] We start with the special case where $n$ is a prime power. Lemma: We always have \[ S(p^e) = \sum_{x \in A(p^e)} x^k \equiv 0 \pmod{p^{e-1}}. \] Proof. For $p$ odd, this follows by taking a primitive root modulo $p^{e-1}$. In the annoying case $p = 2$, the proof is broken into two cases: for $k$ odd it follows by pairing $x$ with $2^e-x$ and when $k$ is even one can take $5$ as a generator and do a similar proof as in the first case. $\blacksquare$ Corollary: We have $\nu_p(1^k + \dots + t^k) \ge \nu_p(t) - 1$ for any $k$, $t$, $p$. Proof. Assume $p \mid t$. Discard the terms in that sum divisible by $p$ and apply the lemma a bunch of times. $\blacksquare$ Now the idea is to add primes $q$ one at a time to $n$, starting from the base case $n = p^e$. So, formally we proceed by induction on the number of prime divisors of $n$. First, suppose we want to go from $n$ to $nq$ where $q \nmid n$. In that case $\varphi(nq)$ gained $\nu_p(q-1)$ factors of $p$ and then we need to show $\nu_p(S(nq,k)) \ge \nu_p(\varphi(n)) + \nu_p(q-1)$. The trick is to write \[ A(nq) = \left\{ a + nh \mid a \in A(n) \text{ and } h = 0,\dots,q-1 \right\} \setminus qA(n) \]and then expand using binomial theorem: \begin{align*} S(nq, k) &= \sum_{a \in A(n)} \sum_{h=0}^{q-1} (a+nh)^k - \sum_{a \in A(n)} (qa)^k \\ &= \sum_{j=0}^k \sum_{a \in A(n)} \sum_{h=0}^{q-1}\binom kj a^{k-j} (nh)^j - q^k S(n,k) \\ &= \sum_{j=0}^k \sum_{h=1}^{q-1} S(n,k-j) \binom kj n^j h^j - q^k S(n,k) \\ &= (q-q^k) S(n,k) + \sum_{j=1}^k S(n,k-j) \binom kj n^j \sum_{h=1}^{q-1} h^j. \end{align*}We claim every term here has enough powers of $p$. For the first term, $S(n,k)$ has at least $\nu_p(\varphi(n))$ factors of $p$; and we have the $q-q^k$ multiplier out there. For the other terms, we apply induction to $S(n,k-j)$; moreover $\sum_{h=1}^{q-1} h^j$ has at least $\nu_p(q-1)-1$ factors of $p$ by corollary, and we get one more factor of $p$ (at least) from $n^j$. On the other hand, if $q$ already divides $n$, then this time \[ A(nq) = \left\{ a + nh \mid a \in A(n) \text{ and } h = 0,\dots,q-1 \right\}. \]and we have no additional burden of $p$ to deal with; the same calculation gives \[ S(nq,k) = qS(n,k) + \sum_{j=1}^k S(n,k-j) \binom kj n^j \sum_{h=1}^{q-1} h^j. \]which certainly has enough factors of $p$ already.

v_Enhance wrote: I thought this was medium-hard, but woww it takes forever to write up. It took me over an hour to write all of this together. I'd have to agree with this. I had the problem pretty much solved at 2:30 but didn't finish the writeup until 3:45.

I solved #1 in 40 minutes, but then couldn't even crack either 2 or 3 in the remaining 230 minutes... I feel like a failure Also #2 and #3 were... wow

If I had time (not wasted on P1 and P2), I would have swept. Now I'm salty about missing an easy #3

i am still confused how using 5 as a generator of a multiplicative modulo 2^e-1 group proves the lemma, and btw (@above) how did you find out that 5 is a generator for 2^e-1? because 5 is not a generator for mod 2^3 or 2^4.. multiplicative groups..

This proof is divided into two parts. The first is reducing the problem to squarefree $n$, and the second is solving it for squarefree $n$. Reducing to Squarfree Let $\Phi(n)$ be the set of numbers less than or equal to $n$ that are relatively prime to $n$. Note that $\varphi(n)=|\Phi(n)|$. We will need an important lemma. Lemma 1: If $r\mid x$, then $\Phi(xr)=\Phi(x)\cup(\Phi(x)+x)\cup(\Phi(x)+2x)\cup\cdots\cup(\Phi(x)+(r-1)x)$. Proof of Lemma 1: The main point here is that $\gcd(y,xr)=1$ if and only if $\gcd(y,x)=1$. The left hand side is simply those numbers that are relatively prime to $x$ and are at most $rx$. $\blacksquare$ Here is the main claim. Claim 1: If $p\mid n'$ and the problem holds for $n'$, then it also holds for $n=pn'$. Proof of Claim 1: Let $m'=\varphi(n')$, and let $m=\varphi(n)=pm'$. We want to show that $m$ divides \[S:=\sum_{a\in\Phi(n)}a^k.\]By lemma 1, we can rewrite this as \[S = \sum_{a\in\Phi(n')}\sum_{\ell=0}^{p-1}(a+n'\ell)^k.\]We now see that \begin{align*} S &= \sum_{a\in\Phi(n')}\sum_{\ell=0}^{p-1}\sum_{j=0}^k\binom{k}{j}a^{k-j}(n'\ell)^j \\ &= \sum_{j=0}^k\binom{k}{j}\left(\sum_{\ell=0}^{p-1}(n'\ell)^j\sum_{a\in\Phi(n')}a^{k-j}\right) \end{align*}Note that $\sum_{a\in\Phi(n')}a^{k-j}$ is a multiple of $m'=m/p$ by the premise of the claim. For $j=0$, the summand looks like $p\sum_{a\in\Phi(n')}a^{k-j}$, which is then a multiple of $p$, and for $j\ge 1$, we see that $p\mid(n'\ell)^j$ (we had $p\mid n'$), so the terms are all divisible by $m$ anyway. Therefore, we see that $m\mid S$, as desired. $\blacksquare$ If the problem is true for $n=p_1\cdots p_k$, then by the claim, it is true for $n=p_1^{e_1}\cdots p_k^{e_k}$ for all $e_1,\ldots,e_k\ge 1$ (essentially by induction), so this part of the overall proof is complete. Solving for Squarefree This part is significantly harder than the previous part, and it will also employ the condition that all primes that divide $\varphi(n)$ divide $n$. Suppose the problem is true for $n'=p_1\cdots p_r$. Now suppose $n=n'p$ where we have that $\varphi(p)=p-1=p_1^{a_1}\cdots p_r^{a_r}$ for some $a_1,\cdots a_r\ge 0$, and not all are $0$. We show that the problem is true for $n$ as well. We are going to need a somewhat ad-hoc lemma for this. Lemma 2: Let $S_k(x)=\sum_{j=1}^{x}j^k$. Viewing $S_k(x)$ as a polynomial in $x$, we can write it as $\frac{x}{(k+1)!}$ times an integer polynomial. Proof of Lemma 2: We proceed by induction on $k$. $k=0$ is obvious, so assume its true for all $k'<k$. Note that \[x^{k+1}=\sum_{j=1}^{x}(j^{k+1}-(j-1)^{k+1})=\sum_{j=1}^{x}\sum_{\ell=0}^{k}\binom{k+1}{\ell}j^\ell(-1)^{k+1-\ell}.\]Therefore, there are integers $c_\ell$ such that \[x^{k+1}=\sum_{\ell=0}^k c_\ell S_\ell(x).\]In particular, $c_k=\pm(k+1)$. We note that \[\sum_{\ell=0}^{k-1}c_\ell S_\ell(x)\]is divisible by $x$ and can be written as an integer polynomial over $\mathrm{lcm}(1!,2!,\ldots,k!)=k!$ by the inductive hypothesis. Therefore, \[(k+1)S_k(x) = \pm x^{k+1}+\frac{xp(x)}{k!}\]for some integer polynomial $p(x)$. Dividing by $k+1$, the result follows by induction. $\blacksquare$ We first need a modification of lemma 1. Here, we see that \[\Phi(n) = \left(\Phi(n')\cup(\Phi(n')+n')\cup\cdots\cup(\Phi(n')+(p-1)n')\right)\setminus\{p\Phi(n')\cup p^2\Phi(n')\cup p^3\Phi(n')\cdots\}.\]However, we have that $p\Phi(n')\subset\Phi(n')$ since $\gcd(p,n')=1$, so in fact \[p\Phi(n')\supset p^2\Phi(n')\supset p^3\Phi(n')\supset\cdots.\]Therefore, we just have \[\Phi(n) = \left(\Phi(n')\cup(\Phi(n')+n')\cup\cdots\cup(\Phi(n')+(p-1)n')\right)\setminus\{p\Phi(n')\}.\]Thus, \[S:=\sum_{a\in\Phi(n)}a^k = \sum_{a\in\Phi(n')}\sum_{\ell=0}^{p-1}(a+n'\ell)^k-p^k\sum_{a\in\Phi(n')}a^k.\]As in the previous part, we can reduce this to \[S=\sum_{j=0}^k\binom{k}{j}\left(\sum_{\ell=0}^{p-1}(n'\ell)^j\sum_{a\in\Phi(n')}a^{k-j}\right)-p^k\sum_{a\in\Phi(n')}a^k.\]Note that this can be viewed is a linear combination of the $x_g:=\sum_{a\in\Phi(n')}a^g$ where $g\ge 0$, and since each of these are divisibly by $\varphi(n')$, it suffices to show that each of their coefficients is divisible by $\varphi(n)/\varphi(n')=\varphi(p)=p-1$. Note that the coefficient of $x_0$ is $p-p^k$, which is clearly divisble by $p-1$, as desired. We now look at the coefficient of $x_{k-g}$ where $g\ge k-1$. We see that it is \[c_g = \binom{k}{g}(n')^g\sum_{\ell=0}^{p-1}\ell^g.\]By lemma 2, $c_g/(p-1)$ is then some integer times $(n')^g/(g+1)!$. Now $\nu_{p_i}((n')^g)=g$, and $\nu_{p_i}((g+1)!)<\frac{g+1}{p_i-1}\le g+1$ by Legendre's theorem. Therefore, $\nu_{p_i}((n')^g/(g+1)!)\ge 0$. Therefore, $\nu_{p_i}(c_g/(p-1))\ge 0$ for all $1\le i\le r$. Here is where the problem's premise comes in. Note that all of the prime factors of $p-1$ are of the form $p_i$, so if $\nu_{p_i}(c_g/(p-1))\ge 0$ for all $p_i$, then in fact $c_g/(p-1)$ is an integer. Thus, $\varphi(p)=p-1\mid c_g$ for all $0\le g\le k$, and we have $\varphi(n')\mid x_g$ for all $0\le g\le k$. Thus, \[\varphi(n)=\varphi(p)\varphi(n')\mid S=c_0x_0+\cdots+c_kx_k.\] Therefore, we have gotten from $p_1\cdots p_r$ to $p_1\cdots p_rp$. The case of $r=0$ is trivially satisfied, so by induction, we have solved the problem for all squarefree $n$. Combining part 1 and part 2 solves the problem. $\blacksquare$

CantonMathGuy wrote: Note that $1^r + \dots + (p - 1)^r$ is $\tfrac{p - 1}{r!}$ times an integer. I proved everything except for this, it is a corollary of Faulhabers but does anybody have a proof for this?

@above I think this should clear your doubts.

Suppose that $n$ works, and $p|n$. Then, I claim that $pn$ works. If the set $S_n$ is the set of numbers which are relatively prime and less than $n$, then $S_{pn}=\{jn+i|j\in[0,p-1],i\in S_n\}$. Now, we have that $$\sum_{i\in S_{pn}}i^k=\sum_{i\in S_{n}}\sum_{j=0}^{p-1}(jn+i)^k=\sum_{i\in S_{n}}\sum_{j=0}^{p-1}\sum_{m=0}^k (jn)^mi^{k-m}\binom{k}{m}=\left(\sum_{i\in S_{n}}\sum_{j=0}^{p-1}\sum_{m=1}^k (jn)^mi^{k-m}\binom{k}{m}\right)+p\sum_{i\in S_{n}}i^k$$The latter term is obviously divisible by $p\phi(n)=\phi(pn)$, as $n$ works. For the left sum, consider the value for a single $m$. We have $\binom{k}{m}n^m\sum_{i\in S_{n}}\sum_{j=0}^{p-1} j^mi^{k-m}=\binom{k}{m}n^m\sum_{j=0}^{p-1}j^m\sum_{i\in S_{n}}i^{k-m}$. It is not hard to see that the first sum is divisible by $p$, and the latter is divisible by $\phi(n)$, so this is also divisible by $\phi(pn)$. Now, we only need to look at if $n$ is squarefree. Before we continue, we present a lemma: Lemma: Given the sum $1^k+2^k+\ldots+n^k$, we can express it as $\frac{nP(n)}{(k+1)!}$, where $P(n)$ is an integer polynomial in $n$. Proof: We will use strong induction. The base case is trivial, so suppose that this works for all numbers less than $a$. Note that $x^{a+1}-(x-1)^{a+1}=(a+1)x^a-\binom{a+1}{2}x^{a-1}+\ldots+(-1)^a$. Summing this from $x=1$ to $n$, the LHS telescopes to $n^{a+1}$, whereas the RHS becomes $(a+1)K_a-\binom{a+1}{2}K_{a-1}+\ldots+(-1)^a$, where $K_i$ denotes the sum $1^i+\ldots+n^i$. So, we know that $K_a=\frac{1}{a+1}\left(n^{a+1}+\binom{a+1}{2}K_{a-1}-\ldots\right)$. The polynomial in the parentheses, after being put under a common denominator, can be written as $\frac{nP(n)}{a!}$, by inductive hypothesis, so $K_a=\frac{nP(n)}{(a+1)!}$, as desired. Note that $v_p((a+1)!)=\sum_{i=1}^\infty\left\lfloor\frac{a+1}{p^i}\right\rfloor<\sum_{i=1}^\infty\frac{a+1}{p^i}=\frac{a+1}{p-1}\le a+1$, so $v_p((a+1)!)\le a$. Now, for the squarefree case, we can use induction on the number of primes going into $n$. Note that if we have a squarefree number $p_1p_2\ldots p_k$ with $p_1<p_2<\ldots<p_k$ which satisfies the problem's precondition (i.e. concerning $\phi(n)$ and $n$), then $n'=p_1p_2\ldots p_{k-1}$ does as well. This is because if it didn't, then there exists a prime $q|\phi(n')$ which doesn't divide $n'$. As $q<p_{k-1}<p_k$, it won't divide $n'p_k$ either. So, the induction is valid if we use larger and larger primes. For the base case, $n$ is a prime. Only $p=2$ satisfies the problem precondition, and this obviously works since $1|1$. Now, suppose that $n=p_1\ldots p_k$ works. We claim that if $N=p_1\ldots p_kq$ such that $q>p_i$, and any prime which divides $q-1$ also divides $n$, then $N$ satisfies the problem statement. Performing a similar trick as before, $$\sum_{i\in S_{N}}i^k=\sum_{i\in S_{n}}\sum_{j=0}^{q-1}(jn+i)^k-\sum_{i\in S_n}(qi)^k$$We subtract the latter term because some of the summands we get in the first summation are divisible by $q$. These are precisely those which are relatively prime to $n$, but not to $N$, and it can be seen that they are exactly $\{qi|i\in S_n\}$. Expanding the first summation, we get $\sum_{i\in S_n}\sum_{j=0}^{q-1}\sum_{m=0}^k (jn)^mi^{k-m}\binom{k}{m}$. If $m=0$, then we get $\sum_{i\in S_n}qi^k$. This minus the second summation is $-q(q^{n-1}-1)\sum_{i\in S_n} i^k$, which is divisible by $(q-1)\phi(n)=\phi(N)$. So, we need $$(q-1)\phi(n)\bigg\arrowvert\sum_{i\in S_n}\sum_{j=0}^{q-1}\sum_{m=1}^k (jn)^mi^{k-m}\binom{k}{m}$$Swapping the sums, this becomes $\sum_{m=1}^k\binom{k}{m}\sum_{i\in S_n}i^{k-m}\left(\sum_{j=0}^{q-1}(jn)^m\right)$. It remains to show that $$q-1\bigg|n^m\sum_{j=0}^{q-1} j^m$$From our lemma, we know that the summation can be written as $\frac{(q-1)C}{(m+1)!}$ for some constant $C$. Now, consider the largest factor $F$ of $(m+1)!$ which goes into $q-1$. The summation is divisible by $\frac{q-1}{F}$. However, we know that $v_p(F)\le m$ for all primes, and for any $p|F$, $p|n$ as well. So, $F|n^m$, and we get the desired result.

We'll induct the statement. First, the statement is clearly true for a single prime $n = p$. Let $A(n)$ denote the set of elements which are relatively prime to $n$. Therefore, the RHS is simply \[ \sum_{i \in A(n)} i^k \]Now, we'll prove a stronger statement, which is \[ \nu_p ( \varphi(n) ) \le \nu_p \left( \sum_{i \in A(n)} i^k \right) \]for any nonnegative integer $k$. Suppose we have \[ \nu_p ( \varphi(n) ) \le \nu_p \left( \sum_{i \in A(n)} i^k \right) \]for a fixed integer $n$ and any integer $k$. Now, we divide to two cases: $\textbf{Case 01.}$ We induct from $n \to np$, where $p | n$. Notice that \[ A(np) = \{ a + nm, a \in A(n), m = 0, 1, 2, \dots, p - 1 \}\]Therefore, we will have to prove that \[ \nu_p ( \varphi(n)) + 1 \le \nu_p \left( \sum_{i \in A(np)} i^k \right) \]But, notice that \begin{align*} \sum_{i \in A(np)} i^k &= \sum_{a \in A(n)} \sum_{m = 0}^{p - 1} (a + nm)^k \\ &= \sum_{a \in A(n)} \sum_{m = 0}^{p - 1} \sum_{i = 0}^k \binom{k}{i} a^{k - i} (nm)^{i} \\ &= \sum_{a \in A(n)} \sum_{m = 0}^{p - 1} a^k + \sum_{a \in A(n)} \sum_{m = 0}^{p - 1} \sum_{i = 1}^{k} \binom{k}{i} a^{k - i} (nm)^{i} \\ &= p \sum_{a \in A(n)} a^k + n \sum_{a \in A(n)} \sum_{m = 0}^{p - 1} \sum_{i = 1}^k \binom{k}{i} a^{k - i} n^{i - 1} m^i \end{align*}Now, notice that when $p | n$, then $\nu_p (n) = \nu_p (\varphi(n)) + 1$. Therefore, we must have \[ \nu_p \left( \sum_{i \in A(np)} i^k \right) \ge \nu_p (\varphi(n)) + 1 = \nu_p (\varphi(np)) \]by the hypothesis of induction. Otherwise, for other prime $r | n$ but $r \not= p$, then we will have \[ \nu_r \left( \sum_{i \in A(np)} i^k \right) \ge \nu_r( \varphi(np) ) \]by the hypothesis of induction as well. $\textbf{Case 02.}$ We induct from $n \to nq$ where $q\not| n$. For this case, we need a special lemma to aid our way. $\textbf{Lemma.}$ We have \[ \nu_p \left( \sum_{m = 1}^{c} m^i \right) \ge \nu_p (c) - 1 \]for any $p,c,i \in \mathbb{N}$. $\textit{Proof.}$ This is obviously true when $c \not \equiv 0 \ (\text{mod} \ p)$. So assume $p | c$. Let $\nu_p(c) = x$, and hence $c = p^x \cdot y$ for integer $x$ and $y$ where $(p,y) = 1$. Group the numbers according to their behavior on $\nu_p (n)$. Group the numbers with the same behavior in a group. Therefore, for each group, we want to prove that \[ \nu_p \left( \sum_{x \in A(p^k \cdot y)} x^i \right) \ge k - 1 \]But this is clear by the hypothesis of the first case. Notice that \[ A(nq) = \{ a + nm, a \in A(n), m = 0, 1, 2, \dots, q - 1 \} - q A(n) \]This is because $q$ and $n$ are relatively prime and therefore some of the residues formed by $a + nm$, where $m = 0, 1, 2, \dots, q - 1$ could be $0$ mod $q$ at some point. Hence, \begin{align*} \sum_{i \in A(nq)} i^k &= \sum_{a \in A(n)} \sum_{m = 0}^{q- 1} (a + nm)^k - q \sum_{a \in A(n)} a^k \\ &= \sum_{a \in A(n)} \sum_{m = 0}^{q - 1} \sum_{i = 0}^k \binom{k}{i} a^{k - i} (nm)^{i} - q \sum_{a \in A(n)} a^k \\ &= \sum_{a \in A(n)} \sum_{m = 0}^{q - 1} a^k + \sum_{a \in A(n)} \sum_{m = 0}^{q - 1} \sum_{i = 1}^{k} \binom{k}{i} a^{k - i} (nm)^{i} - q \sum_{a \in A(n)} a^k \\ &= n \sum_{a \in A(n)} \sum_{m = 0}^{q - 1} \sum_{i = 1}^k \binom{k}{i} a^{k - i} n^{i - 1} m^i \\ &= n \sum_{a \in A(n)} \sum_{i = 1}^k \binom{k}{i} a^{k - i} n^{i - 1} \sum_{m = 1}^{q - 1} m^i \end{align*}Now, note that the expression above is definitely divisible by $n$, and therefore for any prime divisor $p$ of $n$, by Lemma, we must have \[ \nu_p \left( \sum_{i \in A(nq)} i^k \right) \ge \nu_p (n)- 1 + \nu_p (q - 1) = \nu_p (\varphi(nq))\]But, we also have $\nu_q (\varphi(nq)) = 0$, so the statement is obviously true.

Solved with eisirrational. For convenience, let $A(n)$ be the set of positive integers less than $n$ that are relatively prime to $n$, so that $|A(n)|=\varphi(n)$. We begin with a lemma: Lemma: For each $n$, $j$, and prime $p$, we have \[\nu_p\left(\sum_{x=1}^nx^j\right)\ge\nu_p(n)-1.\] Proof. Let $e=\nu_p(n)$. Note the following: \[\sum_{x=1}^nx^j\equiv\frac n{p^e}\sum_{x=0}^{p^e-1}x^j\pmod{p^e},\]It will suffice to check $\textstyle\nu_p\left(\sum_{x=0}^{p^e-1}x^j\right)\ge e-1$. Define \[T_k:=\sum_{\nu_p(x)=k}x^j,\quad\text{so that}\quad\sum_{x=0}^{p^e-1}x^j\equiv\sum_{k=0}^eT_k\pmod{p^e}.\]I contend $\nu_p(T_k)\ge e-1$ for each $k$, which will suffice. Fix $k$, and let $g$ be a primitive root modulo $p^{e-k}$. We have \[T_k\equiv p^{kj}\sum_{i=0}^{\varphi(p^{e-k})-1}g^{ij}\equiv\frac{g^{\varphi(p^{e-k})j}-1}{g^j-1}p^{kj}\pmod{p^e}.\]There are two cases: If $p-1\mid j$, then by LTE, \[\nu_p\left(\frac{g^{\varphi(p^{e-k})j}-1}{g^j-1}\right)=\nu_p\left(\varphi\left(p^{e-k}\right)\right)=e-k-1,\]so $\nu_p(T_k)=(e-k-1)+kj\ge e-1$. Otherwise $g^j-1$ contributes no powers of $p$, and \[\nu_p\left(g^{\varphi(p^{e-k})j}-1\right)\ge e-k\]since $g^{\varphi(p^{e-k})j}\equiv1\pmod{p^{e-k}}$, so $\nu_p(T_k)=(e-k)+kj\ge e$. Thus the lemma is proven. $\blacksquare$ Now we induct on the number of (not necessarily distinct) prime factors of $n$. The base case $n=2$ is easy to check. Recall that $n$ is always even, so we now proceed with the inductive step $n\to nq$, where $q$ is prime. Claim: If $q\mid n$ and the problem statement holds for $n$, then it holds for $nq$. Proof. Observe that \[A(nq)=\bigcup_{i=0}^{q-1}(A(n)+in).\]It follows that \begin{align*} \sum_{a\in A(nq)}a^k&=\sum_{i=0}^{q-1}\sum_{a\in A(n)+in}a^k =\sum_{i=0}^{q-1}\sum_{a\in A(n)}(a+in)^k\\ &=\sum_{j=1}^k\left[\binom kjn^j\left(\sum_{i=0}^{q-1}i^j\right)\left(\sum_{a\in A(n)}a^{k-j}\right)\right]+q\sum_{a\in A(n)}a^k \end{align*}Recall that $\varphi(nq)=q\varphi(n)$. This is divisible by $\varphi(n)$ by the inductive hypothesis, and there are evidently enough factors of $q$. $\blacksquare$ Claim: If $q\nmid n$ and the problem statement holds for $n$, then it holds for $nq$. Proof. Instead, observe that \[A(nq)=\bigcup_{i=0}^{q-1}(A(n)+in)\setminus qA(n).\]As computed above, we have \[\sum_{a\in A(nq)}a^k=\sum_{j=1}^k\left[\binom kjn^j\left(\sum_{i=0}^{q-1}i^j\right)\left(\sum_{a\in A(n)}a^{k-j}\right)\right]-\left(q^k-q\right)\sum_{a\in A(n)}a^k\]Here $\varphi(nq)=(q-1)\varphi(n)$. As in the first claim, this is divisible by $\varphi(n)$, so it suffices to verify there are enough factors of $p$ for $p\mid q-1$. The term $\textstyle(q^k-q)\sum_{a\in A(n)}a^k$ is divisible by $(q-1)\varphi(n)$, so it remains to check each term of the left summation. Indeed, the $n^j$ term contributes at least $1$ factor of $p$, the $\textstyle\sum_{i=0}^{q-1}i^j$ term contributes at least $\nu_p(q-1)-1$ factors of $p$ (by the lemma), and the $\textstyle\sum_{a\in A(n)}a^{k-j}$ contributes $\nu_p(\varphi(n))$ factors of $p$. The inductive step follows. $\blacksquare$

TheUltimate123 wrote:

Proof of the lemma is missing the case $p=2$ since there is no primitive root for powers of $2$ except $2$ and $4$.

We build $n$ by multiplying in its (not necessarily distinct) prime factors. Call $n$ good if $\phi(n)\mid a_1^k+\cdots+a_{\phi(n)} ^k$. Claim: Suppose $p\mid n$. Then $n$ good implies $np$ good. Proof: The list of relatively prime numbers to $np$ is simply the list for $n$ copied $p$ times, and each time, we add $n$ to each the group. So the sum for $np$ is \begin{align*} S&=\sum_{x=0}^{p-1} [(a_1+xn)^k+\cdots+(a_m+xn)^k] = \sum_{x=0}^{p-1} \sum_{y=1}^m (a_y+xn)^k \\ &= \sum_{x=0}^{p-1} \sum_{y=1}^m \sum_{z=0}^k \binom{k}{z} a_y^{k-z} (xn)^z = \sum_{z=0}^k \sum_{x=0}^{p-1} \left[ \binom{k}{z} (xn)^z \sum_{y=1}^m a_y^{k-z} \right] \\ &= \sum_{z=1}^k \sum_{x=0}^{p-1} \left[\binom{k}{z}(xn)^z\sum_{y=1}^m a_y^{k-z}\right]+\sum_{x=0}^{p-1}\sum_{y=1}^m a_y^k. \end{align*}We want to show $\phi(np)=p\phi(n) \mid S$. We already know $\phi(n)\mid \sum_{y=1}^m a_y^{k-z}$ for all $z$ since $n$ good means it holds for all $k$. So $\phi(n)$ divides every term of the above, which means $\phi(n)\mid S$. It remains to show that $\nu_p(S) \ge \nu_p(\phi(n))+1$. The former term: We know $\nu_p(\sum_{y=1}^m a_y^{k-z}) \ge \nu_p(\phi(n))$, and also $\nu_p((xn)^z) \ge \nu_p(n) \ge 1$, so $\nu_p$ of the entire double sum is at least $\nu_p(\phi(n))+1$. The latter term: The ``double sum'' here is simply $p\sum_{y=1}^m a_y^k$. We know $\phi(n) \mid \sum_{y=1}^m a_y^k$, so the $\nu_p$ of this term is at least $\nu_p(\phi(n))+1$. This proves the claim. $\blacksquare$ Lemma: For primes $p,q$, with $q\mid p-1$, and a fixed $z$, we have \[ \nu_q\left(1^z+\cdots+(p-1)^z\right) \ge \nu_q(p-1)-1.\] Proof: Let $e=\nu_q(p-1)$. We want to show $S:=1^z+\cdots+(p-1)^z\equiv 0 \pmod{q^{e}}$. Let $g$ be a primitive root mod $q^{e}$. The issue is that this does not generate multiples of $q$. So we add in $q^z$ times the sum of powers of primitive roots mod $q^{e-1}$. This does not get multiples of $q^2$, so we add in $q^{2z}$ times the sum of power of primitive roots mod $q^{e-2}$, and so on. \begin{align*} S&= 1^z+\cdots+(p-1)^z \\ &\equiv \frac{p-1}{q^e}[(g_1^0+g_1^{z}+\cdots+g_1^{(\phi(q^e)-1)z}) + q(g_2^0+g_2^z+\cdots+g_2^{(\phi(q^{e-1})-1)z}) + \cdots ] \\ &= \frac{p-1}{q^e}\left[ \frac{g_1^{\phi(q^e)z}-1}{g_1^z-1}+q^z\cdot \frac{g_2^{\phi(q^{e-1})z}-1}{g_2^z-1}+\cdots + q^{(e-1)z} \cdot \frac{g_{e}^{\phi(q)z}-1}{g_{e}^z-1} \right] \pmod{q^e}. \end{align*}We will prove that the general term in the above sum is a multiple of $q^{e-1}$. We want to show $q^{e-1}\mid q^{az}\cdot \frac{g^{\phi(q^{e-a})z}-1}{g^z-1}$, for each $a\in [0,e-1]$. We know $g^{\phi(q^{e-a})z} \equiv 1 \pmod{q^{e-a}}$, so $\nu_q(q^{az}\cdot \frac{g^{\phi(q^{e-a})z}-1}{g^z-1})\ge az+(e-a) \ge e-1$. However, this does not work if $q\mid g^z-1$. Suppose $q\mid g^z-1$. Then by LTE, \begin{align*}\nu_q\left(q^{az}\cdot \frac{g^{\phi(q^{e-a})z}-1}{g^z-1}\right) &= az + [\nu_q(\phi(q^{e-a}))+\nu_q(g^z-1)] - \nu_q(g^z-1) \\ &= az + \nu_q(\phi(q^{e-a}))=az+(e-a-1) \ge e-1. \end{align*}It's worth mentioning that equality occurs in the above bound if $z=1$; this means the $e-1$ cannot be improved to $e$. This proves the lemma. Whew! $\blacksquare$ Claim: Suppose $p\nmid n$. Then $n$ good implies $np$ good. Proof: In this case, the list for $np$ is the list for $n$ copied $p$ times, and each time we add $n$ to the group, but we remove $p$ times the list for $n$. So the sum for $np$ is \begin{align*} S&= \sum_{x=0}^{p-1} \sum_{y=1}^m (a_y+xn)^k - \sum_{y=1}^m (pa_y)^k \\ &= \sum_{x=0}^{p-1}\sum_{y=1}^m \sum_{z=0}^k \binom{k}{z} a_y^{k-z} (xn)^{z} -p^k \sum_{y=1}^m a_y^k \\ &= \sum_{z=0}^k \sum_{x=0}^{p-1} \left[\binom{k}{z}(xn)^z\sum_{y=1}^m a_y^{k-z}\right] - p^k \sum_{y=1}^m a_y^k \\ &= \sum_{z=1}^k \left[\binom{k}{z}n^z\left(\sum_{y=1}^m a_y^{k-z}\right) \left(\sum_{x=0}^{p-1}x^z\right)\right] - (p^k-p) \sum_{y=1}^m a_y^k \end{align*}We want to show $\phi(np)=(p-1)\phi(n) \mid S$. By the same logic as the first claim, $\phi(n)\mid S$. It suffices to prove $\nu_q(S) \ge \nu_q(p-1)+\nu_q(\phi(n))$ for all primes $q\mid p-1$. The former term: We know (1) $\nu_q(\sum_{y=1}^m a_y^{k-z})\ge \nu_q(\phi(n))$, (2) $q\mid p-1 \mid \phi(n)$, so $q\mid n$ as well from the condition in the problem statement. So $\nu_q(n^z) \ge \nu_q(n) \ge 1$, and (3) $\nu_q(\sum_{x=0}^{p-1} x^z) \ge \nu_q(p-1)-1$ by the lemma. Combining these, the $nu_q$ of the entire former term is at least $\nu_q(p-1)+\nu_q(\phi(n))$. The latter term: Since $p-1\mid p^k-p$ and $\phi(n) \mid \sum_{y=1}^m a_y^k$, hence the $\nu_q$ of this term is at least $\nu_q(p-1)+\nu_q(\phi(n))$. This proves the claim for $n\to np$, even in the case where $p\nmid n$. $\blacksquare$ The above claims allow us to multiply in the prime factors of $n$ one-by-one, even if they are not distinct. The base case is $n=p$ for any prime $p$, which is clearly good, so we are done.

Heeeey... this one is just about primitive roots It's easy to solve, but a little annoying to write a full answer.

work in progress ooh sorry @below ill rewrite to accomodate for that later

But $\frac{n}{m}$ isn't necessarily an integer?

tastymath75025 wrote: For a given integer $n\ge 2$, let $\{a_1,a_2,…,a_m\}$ be the set of positive integers less than $n$ that are relatively prime to $n$. Prove that if every prime that divides $m$ also divides $n$, then $a_1^k+a_2^k + \dots + a_m^k$ is divisible by $m$ for every positive integer $k$. Proposed by Ivan Borsenco Call a number $n$ "good" is for all $q|n$ we mut have $q|\phi(n)$ Define $a_i=\nu_{p_i}(n)$ and $t_i=\nu_{p_i}(n)$,and notice that $t_i \ge a_i+1$ Define $$\mathcal{A}(n):=\{a_1,..............,a_{\phi(n)} \}$$ Claim:- If $p \nmid n$ then $pn$ is a "good" number. Proof:- The sum at the $np$th step is \begin{align*} S&= \sum_{x=0}^{p-1} \sum_{y=1}^m (a_y+xn)^k - \sum_{y=1}^m (pa_y)^k \\ &= \sum_{x=0}^{p-1}\sum_{y=1}^m \sum_{z=0}^k \binom{k}{z} a_y^{k-z} (xn)^{z} -p^k \sum_{y=1}^m a_y^k \\ &= \sum_{z=0}^k \sum_{x=0}^{p-1} \left[\binom{k}{z}(xn)^z\sum_{y=1}^m a_y^{k-z}\right] - p^k \sum_{y=1}^m a_y^k \\ &= \sum_{z=1}^k \left[\binom{k}{z}n^z\left(\sum_{y=1}^m a_y^{k-z}\right) \left(\sum_{x=0}^{p-1}x^z\right)\right] - (p^k-p) \sum_{y=1}^m a_y^=\sum_{z=1}^k \left[\binom{k}{z} n^z \left(\sum_{a_y \in \mathcal{A}} a_y^{k-z} \right)\left(\sum_{x=0}^{p-1}x^z\right)\right] -(p^k-p) \sum_{a_j \in \mathcal{A}} a_j^k \end{align*}The last expression by strong induction on $n,p$ has a $v_{p_i}$ of atleast $t_p+1$ and all other factors remain same(and $p-1$ clearly divides it),whence this is proved.$\blacksquare$ Define $W_{i,k}$ as the $v_{p_i}$ of $$a_1^k+a_2^k + \dots + a_m^k$$at the $k$th step. Claim:- If $p|n$ then $pn$ works. Proof:- Again direct computation yeilds \begin{align*} S&=\sum_{x=0}^{p-1} [(a_1+xn)^k+\cdots+(a_m+xn)^k] = \sum_{x=0}^{p-1} \sum_{y=1}^m (a_y+xn)^k \\ &= \sum_{x=0}^{p-1} \sum_{y=1}^m \sum_{z=0}^k \binom{k}{z} a_y^{k-z} (xn)^z = \sum_{z=0}^k \sum_{x=0}^{p-1} \left[ \binom{k}{z} (xn)^z \sum_{y=1}^m a_y^{k-z} \right] \\ &= \sum_{z=1}^k \sum_{x=0}^{p-1} \left[\binom{k}{z}(xn)^z\sum_{y=1}^m a_y^{k-z}\right]+\sum_{k=0}^{p-1}\sum_{y=1}^m a_y^k. \end{align*}It suffices to show that the $v_{p_i}$ of this is strictly greater than $\phi(n)=a$ i.e $$\nu_{p} \left[\sum_{x=0}^{p-1}\sum_{y=1}^m a_y^k \right] \ge a_i+1$$However this expression has a $v,_p$ of atleast $\max(W_1,W_2,.......,W_{\nu_p(n)}) \ge a+2>a+1$.$\blacksquare$ Consider intervals $$\left[[1,2,3,.........,p-1] \cup [p+1,..........,2p-1] ............. \cup \left[\left(\frac{n}{p_i}-1 \right) p+1.......... \right] \right]$$Keep adding and subtracting elements from this until we get $\mathcal{A}(n)$ and use PIE to sum up to get $$\sum_{j=1}^{w(n)} |A(p_j)|-\sum_{j=1}^{w(n)} \sum_{k=1}^{w(n)} A|p_jp_k|...............+(-1)^{\tau(n)} p_1...........p_{w(n)}$$which is divisible by $\phi(n)$ using claims 1 and 2. We finish by Newton's sums on $$F(x): \stackrel{\text{def}}{=} (x-{p_1})(x-{p_2})..............(x-{p_k})$$by showing that $\phi(n)|S_k$.$\blacksquare$

Solved with rama1728. Lemma: For any nonnegative integer $k,$ $v_p(1^k+2^k+ \dots + n^k) \ge v_p(n)-1.$ Proof: Let $v_p(n) = l.$ It suffices to prove $v_p(1^k+2^k+ \dots + (p^l-1)^k) \ge l-1.$ We prove with induction on $l$ with base case trivial. Note $1^k+2^k+ \dots + (p^l-1)^k \equiv (bp^l+1)^k+(bp^l+2)^k+ \dots + ((b+1)p^l-1)^k \pmod{p^{l}}$ for any integer $b,$ which is enough for the inductive step. $\square$ Let $S_{n,k}$ be the sum of the $k$th powers of all the positive integers less than $n$ that are relatively prime to $n$. We prove the generalization: for any positive integer $n$ and nonnegative $k,$ $$v_p(\phi(n)) \le v_p(S_{n,k}).$$This is easy for all prime powers $n$ by the lemma. Suppose $n$ works and we want to show $nq$ works, for a prime $q.$ Case 1: $q \mid n.$ Then $v_p(\phi(nq)) - v_p(\phi(n)) = v_p(q) = 0.$ So we want $v_p(S_{nq,k}) \ge v_p(\phi(n)).$ Note \begin{align*} S_{nq,k} &= \sum_{\gcd(a,n) = 1} \sum_{i=0}^{q-1}(a+in)^{k} \\ &= \sum_{\gcd(a,n) = 1} \sum_{i=0}^{q-1} \sum_{j = 0}^{k} \left( \binom{k}{j} a^{k-j} i^j n^j \right) \\ &= \sum_{j = 0}^{k}\binom{k}{j} n^j \left( \sum_{\gcd(a,n) = 1}a^{k-j} \right)\left(\sum_{i=0}^{q-1} i^j \right).\\ \end{align*}Each term has $v_p$ at least $\sum_{\gcd(a,n) = 1}a^{k-j} = v_p(S_{n, k-j})$ for some $j$ which is $\ge v_p(\phi(n))$ (since we assume $n$ works) as desired. $\square$ Case 2: $q \nmid n.$ Then $v_p(\phi(nq)) - v_p(\phi(n)) = v_p(q-1).$ So we want $v_p(S_{nq,k}) \ge v_p(\phi(n)) + v_p(q-1).$ Note \begin{align*} S_{nq,k} &= \sum_{\gcd(a,n) = 1} \sum_{i=0}^{q-1}(a+in)^{k} - \sum_{\gcd(a,n=1)} (qa)^k\\ &= \sum_{\gcd(a,n) = 1} \sum_{i=0}^{q-1} \sum_{j = 0}^{k} \left( \binom{k}{j} a^{k-j} i^j n^j \right) - q^k S_{n,k} \\ &= \sum_{j = 0}^{k}\binom{k}{j} n^j \left( \sum_{\gcd(a,n) = 1}a^{k-j} \right)\left(\sum_{i=0}^{q-1} i^j \right) - q^k S_{n,k}.\\ \end{align*}And since $v_p((q^k-q)S_{n,k}) \ge v_p((q-1)S_{n,k}) \ge v_p(\phi(n)) + v_p(q-1)$ by the inductive hypothesis, it suffices to show $$\sum_{j = 0}^{k}\binom{k}{j} n^j \left( \sum_{\gcd(a,n) = 1}a^{k-j} \right)\left(\sum_{i=0}^{q-1} i^j \right) - q S_{n,k} = \sum_{j = 1}^{k}\binom{k}{j} n^j \left( \sum_{\gcd(a,n) = 1}a^{k-j} \right)\left(\sum_{i=0}^{q-1} i^j \right).$$has a sufficiently high $v_p$ (note that the $j=0$ term has been cancelled). The $\sum_{\gcd(a,n) = 1}a^{k-j} = S(n, k-j)$ has a $v_p$ of at least $v_p(\phi(n))$ (since we assume $n$ works). By the lemma, the $\sum_{i=0}^{q-1} i^j$ has a $v_p$ of at least $v_p(q-1)-1.$ Finally, since $p \mid n,$ $p \mid n^j.$ So each term of the summation has the required $v_p$ as desired. $\blacksquare$

Let $S_{n,k}$ be the sum of the $k$th powers of all the positive integers less than $n$ that are relatively prime to $n$. We need \[ \nu_p(\phi(n)) \le \nu_p(S_{n,k}). \] We start with the following general lemma. Lemma: For $k \ge 0$, $\nu_p(1^k+2^k+ \ldots + n^k) \ge \nu_p(n)-1.$ Proof: We induct on $\nu_p(n)=\ell$ where the base case $\ell=0$ is trivial. The lemma can be reduced to $\nu_p(1^k+2^k+ \ldots + (p^{\ell}-1)^k) \ge \ell-1$. Suppose that $\ell=\ell_0$ works. Then, for $\ell=\ell_0+1$, we have \[ 1^k+2^k+ \ldots + (p^{\ell_0}-1)^k \equiv (ap^{\ell_0}+1)^k+(ap^{\ell_0}+2)^k+ \ldots + ((a+1)p^{\ell_0}-1)^k \pmod{p^{\ell_0}} \]for all integers $a$, so summing the above equivalence for all $0 \le a \le p-1$ finishes the inductive step. $\square$ Consider a positive integer $n$ as happy if it satisfies $\nu_p(\phi(n)) \le \nu_p(S_{n,k})$. To prove the desired result, we use induction; the base case for primes is easy, and the inductive step is summarized in the following two claims. Claim 1: For prime $q$ dividing $n$, $n$ happy implies $nq$ happy. Proof: We have \begin{align*} S_{nq,k} &= \sum_{(a,n) = 1} \sum_{i=0}^{q-1}(a+in)^{k} \\ &= \sum_{(a,n) = 1} \sum_{i=0}^{q-1} \sum_{j = 0}^{k} \left( \binom{k}{j} a^{k-j} i^j n^j \right) \\ &= \sum_{j = 0}^{k}\binom{k}{j} n^j \left( \sum_{(a,n) = 1}a^{k-j} \right)\left(\sum_{i=0}^{q-1} i^j \right) \\ &= \sum_{j=0}^k \binom{k}{q} n^j \left(S_{n, k-j}\right)\left(\sum_{i=0}^{q-1} i^j \right). \end{align*}Note that $p^{\nu_p(\phi(n))}$ divides each $S_{n, k-j}$, so $\nu_p(S_{nq,k}) \ge \nu_p(\phi(n))$, and thus $nq$ is happy. $\square$ Claim 2: For prime $q$ not dividing $n$, $n$ happy implies $nq$ happy. Proof: We have \begin{align*} S_{nq,k} &= \sum_{(a,n) = 1} \sum_{i=0}^{q-1}(a+in)^{k} - \sum_{(a,n)=1} (qa)^k \\ &= \sum_{(a,n) = 1} \sum_{i=0}^{q-1} \sum_{j = 0}^{k} \left( \binom{k}{j} a^{k-j} i^j n^j \right) - \sum_{(a,n)=1} (qa)^k \\ &= \sum_{j = 0}^{k}\binom{k}{j} n^j \left( \sum_{(a,n) = 1}a^{k-j} \right)\left(\sum_{i=0}^{q-1} i^j \right) - \sum_{(a,n)=1} (qa)^k \\ &= \sum_{j=0}^k \binom{k}{q} n^j \left(S_{n, k-j}\right)\left(\sum_{i=0}^{q-1} i^j \right) - \sum_{(a,n)=1} (qa)^k \\ &= \sum_{j=0}^k \binom{k}{q} n^j \left(S_{n, k-j}\right)\left(\sum_{i=0}^{q-1} i^j \right) - q^kS_{n, k} \\ &= \sum_{j=1}^k \binom{k}{q} n^j \left(S_{n, k-j}\right)\left(\sum_{i=0}^{q-1} i^j \right)-(q^k-q)S_{n, k}. \end{align*}Note that $p^{\nu_p(\phi(n))}$ divides each $S_{n, k-j}$, $p^{\nu_p(q-1)-1}$ divides $\sum_{i=0}^{q-1} i^j$, and $p$ divides each $n^j$. Thus, $\nu_p\left( \sum_{j=1}^k \binom{k}{q} n^j \left(S_{n, k-j}\right)\left(\sum_{i=0}^{q-1} i^j \right) \right) \ge \nu_p(\phi(n))+\nu_p(q-1)=\nu_p(\phi(nq))$, and $\nu_p((q^k-q)S_{n,k}) \ge \nu_p((q-1)S_{n,k}) \ge \nu_p(\phi(n)) + \nu_p(q-1)$, so $\nu_p(S_{nq, k}) \ge \nu_p(\phi(nq))$, as required. $\square$ Hence, the above claims complete the proof.