Quadratic Nature by Sum of Floors of Multiples of Fractions

Theorem

An unwieldy name for an unwieldy result.

Let $p$ be an odd prime.

Let $a \in \Z$ be an odd integer such that $p \nmid a$.

Let $\left({\dfrac a p}\right)$ be defined as the Legendre symbol.

Then:

$\left({\dfrac a p}\right) = \left({-1}\right)^{\alpha \left({a, p}\right)}$

where:

$\displaystyle \alpha \left({a, p}\right) = \sum_{k=1}^{\frac {p-1}2} \left \lfloor {\frac {k a} p} \right \rfloor$

and $\displaystyle \left \lfloor {\frac {k a} p} \right \rfloor$ is the floor function of $\dfrac {k a} p$.

Proof

We will borrow some ideas and techniques from the proof of Gauss's Lemma.

Let $S = \left\{{a, 2a, 3a, \ldots, \dfrac {p-1} 2 a}\right\}$.

Let us create $S'$ from $S$ by replacing each element of $S$ by its least positive residue modulo $p$.

Arranging $S'$ into increasing order, we get:

$S' = \left\{{b_1, b_2, \ldots, b_m, c_1, c_2, \ldots, c_n}\right\}$

where $b_m < \dfrac p 2 < c_1$ and $m + n = \dfrac {p-1}2$.

According to the Division Theorem, we can divide any $k a \in S$ by $p$ and get:

$k a = p \times \left \lfloor {\dfrac {k a} p} \right \rfloor + r$

where $r \in S'$.

Let $k$ run from $1$ to $\dfrac {p-1}2$ and add up the resulting equations.

We get:

$\displaystyle (1): \qquad \sum_{k=1}^{\frac {p-1}2} k a = \sum_{k=1}^{\frac {p-1}2} p \times \left \lfloor {\frac {k a} p} \right \rfloor + \sum_{i=1}^{m} b_i + \sum_{j=1}^{n} c_j$

As in the proof of Gauss's Lemma, all the remainders are in fact distinct elements of $S'$.

From the proof of Gauss's Lemma again, we have that:

$\displaystyle S'' = \left\{{b_1, b_2, \ldots, b_m, p-c_1, p-c_2, \ldots, p-c_n}\right\} = \left\{{1, 2, 3, \ldots, \frac {p-1} 2}\right\}$

Adding up all the elements of $S''$ we have:

$\displaystyle \sum_{k=1}^{\frac {p-1}2} k = \sum_{i=1}^{m} b_i + \sum_{j=1}^{n} \left({p - c_j}\right) = \sum_{i=1}^{m} b_i + p n - \sum_{j=1}^{n} c_j$

Subtracting this equation from $(1)$ above gives us:

$\displaystyle \sum_{k=1}^{\frac {p-1}2} k a - \sum_{k=1}^{\frac {p-1}2} k = \sum_{k=1}^{\frac {p-1}2} p \times \left \lfloor {\frac {k a} p} \right \rfloor + 2 \sum_{j=1}^{n} c_j - p n$

That is:

$\displaystyle \left({a - 1}\right) \sum_{k=1}^{\frac {p-1}2} k = p \times \alpha \left({a, p}\right) + 2 \sum_{j=1}^{n} c_j - p n$

Now we are going to write this equation modulo $2$.

Note that:

• $\displaystyle \left({a - 1}\right) \sum_{k=1}^{\frac {p-1}2} k$ is even, as $a$ is odd
• $\displaystyle 2 \sum_{j=1}^{n} c_j$ is also of course even.

So:

$p \alpha \left({a, p}\right) - p n \equiv 0 \pmod 2$

Since $p$ is odd, this amounts to saying $\alpha \left({a, p}\right) \equiv n \pmod 2$.

From the conclusion of Gauss's Lemma that $\displaystyle \left({\frac a p}\right) = \left({-1}\right)^n$, we have our result.

$\blacksquare$