Online Course Discussion Forum
MCIII Number Theory 1.16 and 1.19
Hello,
Hello! I'm not sure how to start with 1.16.
For 1.19, I tried pairing 1^k with n^k and 2^k with (n-1)^k then use the odd sum of powers formula to get that it is divisible by (n+1)/2 (as we need, since 1+2+...+n=n(n+1)/2). I don't know how to prove that it is divisible by n as well. I tried expanding the other parts but it just gave complicated geometric sequences and I don't know how to proceed.
Thank you,
Tina Jin
For 1.16: Let's look at a few examples as a hint at a general method.
- Let $m=10$ so a reduced residue system is $1, 3, 7, 9$. Then the sum is $1+9+3+7 = 10+10=20\equiv 0 \pmod{10}$.
- Let $m=15$ so a reduced residue system is $1, 2, 4, 7, 8, 11, 13, 14$. Then the sum is $1+14+2+13+4+11+7+8 = 15+15+15+15 = 60\equiv 0 \pmod{15}$.
For 1.19: You're correct to start with $1+2+...+n = n(n+1)/2$. Pairing is also key to this problem, good intuition! You're off to a good start! Be a little careful however, as you only know $(n+1)/2$ is an integer if $n$ is odd. Consider cases for $n$ odd (which starts like you did) and $n$ even. Hint to continue where you left off in the case where $n$ is odd: note that you already know that $n$ is a factor of $n^k$, so consider the rest of the sum to see if you can apply a similar trick.
Social networks