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
Problem
Source: Iran 3rd round 2011-number theory exam-p2
Tags: induction, algebra, polynomial, modular arithmetic, calculus, integration, function
16.09.2011 18:15
$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
16.09.2011 22:07
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?
17.09.2011 05:53
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.
17.09.2011 05:54
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.
17.09.2011 13:32
I really don't understand you. in my example $ \phi(n)=p-1 $ and each number is congruent with $ -1 $ modulo $ p $.
17.09.2011 14:34
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
26.12.2011 14:00
so are there any solution yet ?
10.01.2012 12:00
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.
10.01.2012 20:32
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)?
16.07.2018 19:20
The answer is $\phi (n)$.The method is just dinoboy's method but he made some mistakes when calculating mod $p_i^{e_i}$.
08.09.2020 16:04
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?
but Is it obvious or sth?
23.01.2022 20:01
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
23.01.2022 20:56
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.