2
$\begingroup$

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.

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.