Online Course Discussion Forum

MCIII Number Theory 1.16 and 1.19

 
 
JinTina的头像
MCIII Number Theory 1.16 and 1.19
JinTina - 2023年12月27日 Wednesday 10:41
 

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

 
LensmireJohn的头像
Re: MCIII Number Theory 1.16 and 1.19
LensmireJohn - 2023年12月27日 Wednesday 11:48
 

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.

JinTina的头像
Re: MCIII Number Theory 1.16 and 1.19
JinTina - 2024年01月14日 Sunday 11:30
 
Thank you!