$n$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. for every $p^t$ divided ,$t$ is the number largest and $p-1$ divide $k$ then $p^t$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. You can solve by induction by $t$,s

it's wrong. if $ n=p,k=p-1 $ then the remainder is $ -1 $. I think this is $ \phi(n) $ an I tried to prove this taking $ p^{\alpha} $ the maximum power of $ p $ which divide $ n $ and use induction after $ \alpha $ but I didn't obtained anything. can somebody post a solution?

hungnguyenvn wrote: $n$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. for every $p^t$ divided ,$t$ is the number largest and $p-1$ divide $k$ then $p^t$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. You can solve by induction by $t$,s that wrong because $p$ divided $1+2+3+...+p-1$ . can you review,please? i have solved yet.

hungnguyenvn wrote: $n$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. for every $p^t$ divided ,$t$ is the number largest and $p-1$ divide $k$ then $p^t$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. You can solve by induction by $t$,s that wrong because $p$ divided $1+2+3+...+p-1$ . can you review,please? i have solved by induction yet.

I really don't understand you. in my example $ \phi(n)=p-1 $ and each number is congruent with $ -1 $ modulo $ p $.

hungnguyenvn wrote: hungnguyenvn wrote: $n$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. for every $p^t$ divided ,$t$ is the number largest and $p-1$ divide $k$ then $p^t$ divided $ a _ { 1 } ^ { k } + . . . . . + a _ { \ p h i ( n ) } ^ { k } $. You can solve by induction by $t$,s that wrong because $p$ divided $1+2+3+...+p-1$ . can you review,please? i have solved yet. just read carefully: goodar2006 wrote: Let $n$ and $k$ be two natural numbers such that $k$ is even and for each prime $p$ if $p|n$ then $p-1|k$. let $\{a_1,....,a_{\phi(n)}\}$ be all the numbers coprime to $n$. What's the remainder of the number $a_1^k+.....+a_{\phi(n)}^k$ when it's divided by $n$? proposed by Yahya Motevassel

so are there any solution yet ?

goodar2006 wrote: Let $n$ and $k$ be two natural numbers such that $k$ is even and for each prime $p$ if $p|n$ then $p-1|k$. let $\{a_1,\ldots,a_{\phi(n)}\}$ be all the numbers coprime to $n$. What's the remainder of the number $a_1^k+\cdots+a_{\phi(n)}^k$ when it's divided by $n$? Here is a solution of mine, and it seems ugly. If $n=1$ the remainder is zero. If $n=2$ the remainder then is $1$. Let us assume that $n>2$, then $\phi(n)$ is even. By writing $k=\phi(n)q+r$, we can assume that $0\leq k<\phi(n)$ and $k$ is still even. (It follows from the fact $p\mid n$ implies $p-1\mid \phi(n)$.) Let $e_1=a_1+\cdots+a_{\phi(n)}$, $\ldots$, $e_{\phi(n)}=a_1\cdots a_{\phi(n)}$ be all elementary symmetric polynomial of $\phi(n)$ numbers $a_1,\ldots,a_{\phi(n)}$; and let $s_j=a_1^j+\cdots+a_{\phi(n)}^j$. Applying Newton's identities, we obtain \[ s_k=e_1s_{k-1}-e_2s_{k-2}+\cdots+e_{k-1}s_1-ke_k \] We take a look at two polynomials $(x-a_1)\cdots(x-a_{\phi(n)})$ and $x^{\phi(n)}-1$. They are identical in $\mathbb Z_n[x]$, so $e_j\equiv 0\pmod n$ for any $1\leq j<\phi(n)$. Thus, we get: (a) If $k>0$ then $s_k\equiv 0\pmod n$, so the remainder is zero. (b) If $k=0$ then $s_k\equiv \phi(n)\pmod n$, so the remainder is $\phi(n)$. In summing, in case $n>2$, we have: the remainder is zero if $\phi(n)\nmid k$, and the remainder is $\phi(n)$ in case $\phi(n)\mid k$. QED.

pluricomplex's solution is wrong, choose $n = p^2q^2$ for distinct odd primes $p,q$ and $k = p(p-1)(q-1)$. Then the sum is $\phi(n) \pmod{p^2}$ and $0 \pmod{q^2}$ so mod $n$ it's some strange number but most certainly not either $0,\phi(n) \pmod{p^2q^2}$. His error lies in the fact $(x - a_1)(x-a_2)...(x-a_n)$ and $x^{\phi(n)} - 1$ are NOT identical in $\mathbb{Z}_n[x]$ due to the fact it is not an integral domain so many things deemed as "common sense" or "obvious" are in fact false. For a simple counterexample consult $n=15$, compare this: http://www.wolframalpha.com/input/?i=%28x-1%29%28x-2%29%28x-4%29%28x-7%29%28x-8%29%28x-11%29%28x-13%29%28x-14%29 modulo $15$ with $x^8 - 1$. Here is a solution I came up with. Let $n = p_1^{e_1}p_2^{e_2}...p_m^{e^m} = \prod_{i=1}^m p_i^{e_i}$ for distinct primes $p_i$. Then it suffices to find $\sum_{i=1}^{\phi(n)} a_i^k \pmod{p_i^{e_i}}$ for each $i$. Observe that $\sum_{i=1}^{\phi(n)} a_i^k \equiv \frac{\phi(n)}{\phi(p_i^{e_i})} \sum_{i=1}^{\phi(p_i^{e_i})} b_i^k \pmod{p_i^{e_i}}$ where the $b_i$ are the numbers below $p_i^{e_i}$ which are relatively prime to it. First we examine the case of $p_i = 2$ and $e_i \ge 3$, for $e_i = 1,2$ it's trivial. Using the fact every unit in $\mathbb{Z}/2^k\mathbb{Z}$ can be written as $\pm 3^n \pmod{2^k}$ for some $n$, we quickly find that: $\sum_{i=1}^{\phi(p_i^{e_i})} b_i^k \equiv 0 \pmod{p_i^{e_i}}$ if $2^{e_i-2} \nmid k$, otherwise it's $\phi(p_i^{e_i})$. Now we move onto odd primes $p_i$. Now using the fact that $\mathbb{Z}/p^k\mathbb{Z}$ has a primitive root, we get $\sum_{i=1}^{\phi(p_i^{e_i})} b_i^k \equiv 0 \pmod{p_i^{e_i}}$ unless $\phi(p_i^{e_i})|k$, in which case it is $\phi(p_i^{e_i})$. Thus for each prime $p_i$ which is odd we have $\sum_{i=1}^{\phi(n)} a_i^k \equiv 0 \pmod{p_i^{e_i}}$ if $p_i^{e_i-1}(p-1)\nmid k$, and $\phi(n) \pmod{p_i^{e_i}}$ otherwise if $p_i$ is an odd prime. Let $x$ be the product of prime power that have it $0 \pmod{p_i}$, and $y$ be for $\phi(n) \pmod{p_i^{e_i}}$. Then clearly $\sum_{i=1}^{\phi(n)} a_i^k \equiv 0 \pmod{x}$ and $\sum_{i=1}^{\phi(n)} a_i^k \equiv \phi(n) \pmod{y}$ Then if $x^{-1}$ is the inverse of $x$ modulo $y$ (which exists as obviously $\gcd(x,y) = 1$), then we find: $\sum_{i=1}^{\phi(n)} a_i^k \equiv x \cdot x^{-1} \cdot \phi(n) \pmod{n}$ satisfies both congruences above and therefore this is the form. Would this formula be simply enough to be accepted I'm doubtful, but combining congruences typically will not yield simpler expressions then the one given above... goodar2006 can you verify if this is the answer (or if a simpler one exists)?

The answer is $\phi (n)$.The method is just dinoboy's method but he made some mistakes when calculating mod $p_i^{e_i}$.

dinoboy wrote: Now using the fact that $\mathbb{Z}/p^k\mathbb{Z}$ has a primitive root, we get $\sum_{i=1}^{\phi(p_i^{e_i})} b_i^k \equiv 0 \pmod{p_i^{e_i}}$ unless $\phi(p_i^{e_i})|k$, in which case it is $\phi(p_i^{e_i})$. Sorry If It's obvious , Can s.o explain why is it true? for $p$ as a exponent my proof is the sum becomes $\frac{g^{k \phi(p)} -1}{g^k -1}$ so if $\phi(p) \nmid k$ the the denominator has no $p$ factor and the claim is true, But here by writing as primitive root I get $\frac{g^{k \phi(p^e)}-1}{g^k -1}$ there is a case that $\phi(p^e) \nmid k$ but let's say $p-1 \mid k$ Then the denominator has $p$ as a divisor. Why is it equal to 0 in this case?

I can fix it by generalized LTE

but Is it obvious or sth?

For $n$ to be squarefree let $\sum_{i=1}^{\phi(n)} {a_{i}}^{k} \equiv x (modn)$ $\cdots$ let $\sum_{i=1}^{\phi(n)} {a_{i}}^{k} = E $ write $E=nq+x$ for some ${q}\in{\mathbb{Z}}$ then note that ${E}\equiv{x}(modp)$ $\boxed{claim}$ : ${p}\nmid{a_{i}}$ $\boxed{proof}$ : if ${p}\mid{a_{i}}$ then $gcd(a_{i},n)={p}\times{(gcd(q_{i},X))}$ for $n=pX$ and $a_{i}=pq_{i}$ which is absurd write $k=(p-1)Y$ for some ${Y}\in{\mathbb{Z}}$ now note that by FLT we have : ${{a_{i}}^{k}}\equiv{{{a_{i}}^{(p-1)Y}}}\equiv{1} (mod p)$ as ${{a_{i}}^{p-1}}\equiv{1}(mod p)$ by FLT as ${p}\nmid{a_{i}}$ now we have $$\sum_{i=1}^{\phi(n)} {a_{i}}^{k} \equiv {1+1+1.......1}(\phi(n) times) \equiv {\phi(n)} (mod p)$$so we have $$\sum_{i=1}^{\phi(n)} {a_{i}}^{k} \equiv {\phi(n)} (mod n)$$ @below thanks .... the converse does not hold always true

I believe the above is wrong, since the line above the last one would imply the last statement only if $n$ was squarefree (well, you should find the residue modulo $p_i^{v_{p_i}(n)}$; and yes, it's not that simple, can someone give entirely correct solution?). And also, this kinda reminds of USAMO 2018/3, but is a different problem.