# Quadratic Reciprocity - Legendre Symbols

Find the value of $(\frac{1\cdot 2}{73})+(\frac{2\cdot 3}{73})+...+(\frac{71\cdot 72}{73})$.

This is based off each fraction being a Legendre Symbol.

I tried to find a pattern... but I could't find anything. Also, I tried using Euler's Criterion since 73 is prime, but I still didn't see a fast way to figure this out.

• So... we have 2* all of them except for $((36\cdot 37)/73)$ – Sarah Oct 16 '13 at 3:17
• Am I missing something about the pairing that makes this simple? – Sarah Oct 16 '13 at 3:19

For any odd prime $p$, we write $(\frac{b}{p})$ for the Legendre symbol.
Let $p=73$. For any $a$, let $a^\ast$ be the inverse of $a$ modulo $p$. Then $$(\frac{a(a+1)}{p})=(\frac{a(a+aa^\ast)}{p})=(\frac{a^2(a^\ast+1)}{p})=(\frac{a^\ast+1)}{p}).$$ Add up, $a=1$ to $a=p-2$. As $a$ ranges from $1$ to $p-2$, the least positive residue of $a^\ast+1$ ranges through the integers from $2$ to $p-1$. Thus our sum is equal to $$(\frac{2}{p})+(\frac{3}{p})+\cdots +(\frac{p-1}{p}).$$ this sum is equal to $-(\frac{1}{p})$, which is $-1$.