Gauss won't help

n = 1 10007 n ( n + 1 ) 10009 = ? \sum_{n=1}^{10007}\frac{n(n+1)}{10009} = \, ?

Note: In above summation expression, ( a b ) \large \left( \frac{a}{b} \right) denotes the Legendre symbol and it is not an ordinary fraction.


Bonus: Generalize this for arbitary odd primes.


The answer is -1.

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

Otto Bretscher
Feb 28, 2016

Gauss does help... he was the one who studied this very expression (for arbitrary primes)!

We will find n = 1 p 2 ( n ( n + 1 ) p ) \sum_{n=1}^{p-2}\left(\frac{n(n+1)}{p}\right)

for any odd prime number p p .

For any 0 < n < p 1 0<n<p-1 there exists an 0 < a ( n ) < p 1 0<a(n)<p-1 such that n × a ( n ) 1 ( m o d p ) n\times a(n)\equiv 1 \pmod{p} : the multiplicative inverse.

Now

n = 1 p 2 ( n ( n + 1 ) p ) = n = 1 p 2 ( n ( n + n × a ( n ) ) p ) = n = 1 p 2 ( n 2 ( 1 + a ( n ) ) p ) = a = 1 p 2 ( 1 + a p ) = 1 \sum_{n=1}^{p-2}\left(\frac{n(n+1)}{p}\right)=\sum_{n=1}^{p-2}\left(\frac{n(n+n\times a(n))}{p}\right)=\sum_{n=1}^{p-2}\left(\frac{n^2(1+a(n))}{p}\right)=\sum_{a=1}^{p-2}\left(\frac{1+a}{p}\right)=\boxed{-1}

The last equation holds since ( 1 p ) = 1 \left(\frac{1}{p}\right)=1 is missing from the sum.

Moderator note:

Great explanation of the manipulations that allows us to simplify this calculation.

But for some reason I don't know when I key in this equation in a sigma calculator the answer comes up as 33383352 33383352 . Link to the calculator is here Link

Lee Care Gene - 5 years, 3 months ago

Log in to reply

Did you use the Legendre symbol?

Otto Bretscher - 5 years, 3 months ago

Log in to reply

No. I think thats the reason.

Lee Care Gene - 5 years, 3 months ago

Log in to reply

@Lee Care Gene :3 Thats sooooooooooooooooooooooooo ambiguos ,...................................................................................

Yasharyan Gaikwad - 5 years, 3 months ago

Log in to reply

@Yasharyan Gaikwad I rephrased the problem a bit so that people easily notice that it is Legendre symbol. Hope your ambiguity vanishes :)

Nihar Mahajan - 5 years, 3 months ago

@Yasharyan Gaikwad It is stated in the problem itself.

Calvin Lin Staff - 5 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...