There's gonna be so many solutions

Number Theory Level 5

For an integer k k let T k T_k denote the number of k k -tuples of integers ( x 1 , x 2 , . . . x k ) (x_1, x_2, ...x_k) with 0 ≤ x i < 73 0 \leq x_i < 73 for each i i , such that 73 ∣ x 1 2 + x 2 2 + … + x k 2 − 1 73 \mid x_1^2 + x_2^2 + \ldots + x_k^2 - 1 . Compute the remainder when T 1 + T 2 + . . . + T 2017 T_1 + T_2 + ... + T_{2017} is divided by 2017.


The answer is 2.

Sharky Kesa by Sharky Kesa , 19, United Kingdom

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Corn
Nov 20, 2017

Here's a partial solution. If p = 73 p=73 (and more generally if p ≡ 1 p \equiv 1 mod 4 4 ), I get T k = p k − 1 + ( − 1 ) k + 1 p ⌊ ( k − 1 ) / 2 ⌋ , T_k = p^{k-1} + (-1)^{k+1}p^{\lfloor (k-1)/2 \rfloor}, but I am not sure how to prove it elegantly. Anyway, this shows that T 2 m − 1 + T 2 m = p 2 m − 2 + p 2 m − 1 , T_{2m-1}+T_{2m} = p^{2m-2}+p^{2m-1}, so the sum is ( T 1 + T 2 ) + ( T 3 + T 4 ) + ⋯ + ( T 2015 + T 2016 ) + T 2017 = ( p 0 + p 1 ) + ( p 2 + p 3 ) + ⋯ + ( p 2014 + p 2015 ) + p 2016 + p 1008 = p 2017 − 1 p − 1 + p 1008 \begin{aligned} (T_1+T_2)+(T_3+T_4)+\cdots+(T_{2015}+T_{2016}) + T_{2017} &= (p^0+p^1)+(p^2+p^3)+\cdots+(p^{2014}+p^{2015})+p^{2016}+p^{1008} \\ &= \frac{p^{2017}-1}{p-1}+p^{1008} \end{aligned} Now mod 2017 the first term is just 1 1 and the second term is ( p 2017 ) \left(\frac{p}{2017}\right) (the Legendre symbol ). A quick computation shows that this symbol is 1 , 1, so the answer is 1 + 1 = 2 . 1+1=\fbox{2}.

Anyone want to fill in the gap at the beginning?

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...