Online Course Discussion Forum

MC III Number Theory 1.17,1.18,1.19

 
 
Picture of Alan Ding
MC III Number Theory 1.17,1.18,1.19
by Alan Ding - Friday, 22 March 2024, 9:02 PM
 

May I have some ideas on how to start these? They were not explained in class. Thank you!

 
Picture of Xilong Lin
Re: MC III Number Theory 1.17,1.18,1.19
by Xilong Lin - Friday, 22 March 2024, 11:04 PM
 
Can you please photo the original problem. 
Picture of Alan Ding
Re: MC III Number Theory 1.17,1.18,1.19
by Alan Ding - Saturday, 23 March 2024, 9:44 AM
 


Picture of Alan Ding
Re: MC III Number Theory 1.17,1.18,1.19
by Alan Ding - Saturday, 23 March 2024, 9:48 AM
 


Picture of Xilong Lin
Re: MC III Number Theory 1.17,1.18,1.19
by Xilong Lin - Sunday, 24 March 2024, 11:24 PM
 
For 1.17, you can look at this https://artofproblemsolving.com/community/c6h1124783p5192873.

For 1.18, consider x^2 = (-x)^2.

For 1.19,write the left and side as n(n + 1)/2.

Good luck. 

Picture of Alan Ding
Re: MC III Number Theory 1.17,1.18,1.19
by Alan Ding - Saturday, 30 March 2024, 9:56 AM
 

I couldn't follow the solutions on AoPS for 1.17, they were too confusing

I tried $m=2,4$ and I figured all sums I tested don't work 

but I can't figure out how to prove it for all m

maybe induction??


$\text{For 1.18}$,

$\text{I tried small values and they all showed that they were not complete residue systems.}$

I tried making $x^2$=$(-x)^2$ like you suggested but I don't really know what to do after that,


I'm figuring out what to do after making the left $\frac{n(n+1)}{2}$ for 1.19





Picture of John Lensmire
Re: MC III Number Theory 1.17,1.18,1.19
by John Lensmire - Saturday, 30 March 2024, 10:55 AM
 

Hi Alan,

To start, it might be good to revisit 1.16 and the extra problem we called 16.5 in the live class. The relevant portions start around 1 Hour and 18 Minutes in the Week 2 Recording. Note: the key idea here is pairing a number a with (m-a). Note (m-a) can also be through of as -a if we're working mod m.

For 1.17, the extra problem 16.5 is actually one easy way to prove the result.

For 1.18, the pairing trick mentioned above is also the key.

For 1.19, it's probably easiest to think of two cases, once for n even and one for n odd. Both cases are similar but it can be easier to think of them separately. As a further hint, if n is even, try to prove (n/2) divides (1^k+...+n^k) and (n+1) divides (1^k+...+n^k). Again pairing will be helpful.

Picture of Alan Ding
Re: MC III Number Theory 1.17,1.18,1.19
by Alan Ding - Tuesday, 9 April 2024, 8:54 PM
 

$\text{I figured out 1.17. Thanks for the help!}$


For 1.18, I couldn't find how to pair anything, maybe $k^2$ and $(m-k)^2$, so I used the fact that a complete residues system does not have repeated values. I couldn't solve it though.


I couldn't figure 1.19.