1
$\begingroup$

I have been working for quite a while on finding a closed formula for the Legendre Symbol. Inspite of my best efforts I can't come anything better with a formula for the symbol $\left(\dfrac{q}{p}\right)$ of the form $$f(q,p)+\displaystyle\sum_{k=1}^{\frac{p-1}{2}}\left(\left \lfloor \dfrac{kq}{p}\right \rfloor-\left \lfloor \dfrac{k(q-1)}{(p-1)}\right \rfloor\right)$$ For two odd primes $p$ and $q$ with $p>q$. The term $f(p,q)$ has a closed form but I can't find a closed form for the second expression. I have searched in the internet for getting any clue as to how to determine the closed form for this function but the only thing that I found was that $\displaystyle\sum_{k=1}^{\frac{p-1}{2}}\left \lfloor \dfrac{kq}{p}\right \rfloor$ in general has no closed form. But it may be the case that the sums individually may have no closed form (though the second sum has a closed form) but the difference has.

Also, not the explicit sum but comments regarding its parity will be enough.

Notice that the sum can be easily obtained if we can find a closed form for the number of points on the boundary lines or within a triangle with vertices $(0,0)$,$\left(\frac{p-1}{2},\frac{q-1}{2} \right)$ and $\left(\frac{p-1}{2},\frac{q(p-1)}{2p} \right)$.

So, is there any method of obtaining a closed formula for the sum? If not, then can some references be given which inspects this kind of sums? Any help will be appreciated.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Do not expect any simple expression for the Legendre function. It is a complicated function in the sense that we cannot answer (even approximately) simple questions like: for a given $q$, how small is the smallest $a\geq 1$ with $\left(\frac{a}{q}\right)=-1$ (cf. en.wikipedia.org/wiki/…). We like quadratic reciprocity (among other things) because it allows us to calculate the Legendre symbol in polynomial time. $\endgroup$
    – GH from MO
    Commented Sep 21, 2014 at 6:34

1 Answer 1

Reset to default
1
$\begingroup$

I am not sure what you mean by "closed formula", but I provide below an identity that might satisfy you. It is a consequence of Gauss's lemma and it implies quadratic reciprocity (for details see Theorems 26 to 29 here).

Theorem. For $a>0$ and $(p,2a)=1$ we have $$\left(\frac{a}{p}\right)=(-1)^{s},\quad\text{where}\quad s:=\sum_{1\leq m\leq a/2} \left(\left\lfloor\frac{mp}{a}\right\rfloor- \left\lfloor\frac{mp}{a}-\frac{p}{2a}\right\rfloor\right).$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer. It is always hard to define a 'closed form expression' but you may have an idea for the meaning of closed form that is intended here. Take for example the simple sum, $$\displaystyle \sum_{k=1}^n k=\dfrac{n(n+1)}{2}$$ The R.H.S formula is the 'closed form' for the sum. Also notice that for my work the explicit expression for the sum isn't needed, only remarks on parity of the sum is needed. $\endgroup$
    – user57432
    Commented Sep 21, 2014 at 6:04
  • 1
    $\begingroup$ @user170039: See my comment to your original post. $\endgroup$
    – GH from MO
    Commented Sep 21, 2014 at 6:32

You must log in to answer this question.