# Prove $∑^{(p−1)/2}_{k=1} \left \lfloor{\frac{2ak}{p}}\right \rfloor \equiv ∑^{(p−1)/2}_{k=1} \left \lfloor{\frac{ak}{p}}\right \rfloor ($mod $2)$

If $p$ is an odd prime number and $a$ is an odd integer not divisible by $p$, then why does

$∑^{(p−1)/2}_{k=1} \left \lfloor{\frac{2ak}{p}}\right \rfloor \equiv ∑^{(p−1)/2}_{k=1} \left \lfloor{\frac{ak}{p}}\right \rfloor ($mod $2)$ ?

• Is this question incorrect? – user274933 Oct 16 '15 at 21:05
• The question is fine; it just seems that either no one has taken a serious crack at it yet, or it’s hard enough that no one who has looked has seen a solution. I make no guarantees, but I have it set aside to look at later if it isn’t answered by the time I get to it. – Brian M. Scott Oct 16 '15 at 21:12

If for an odd prime $p$ and an arbitrary natural number $b$ not divisible by $p$ we write out:

$$\mu_p(b)=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2bk}{p}}\right\rfloor$$

Then using Eisenstein's lemma in his geometric proof of quadratic reciprocity we have:

$$b^{\frac{p-1}{2}}\equiv (-1)^{\mu_p(b)} \text{ mod } p$$

Which as a result gives us:

$$(-1)^{\mu_p(uv)}\equiv (uv)^{\frac{p-1}{2}}\equiv u^{\frac{p-1}{2}}v^{\frac{p-1}{2}}\equiv (-1)^{\mu_p(u)}(-1)^{\mu_p(v)}\equiv (-1)^{\mu_p(u)+\mu_p(v)} \text{ mod } p$$

So that we get:

$$\mu_p(uv)\equiv \mu_p(u)+\mu_p(v)\text{ mod } 2$$

Thus sending $u\to b$ and $v\to \frac{p+1}{2}$ gives us:

$$\mu_p\left(\frac{b(p+1)}{2}\right)\equiv \mu_p(b)+\mu_p\left(\frac{p+1}{2}\right)\text{ mod } 2\\\implies \mu_p(b)\equiv \mu_p\left(\frac{b(p+1)}{2}\right)-\mu_p\left(\frac{p+1}{2}\right)\text{ mod } 2$$

However by definition we have:

$$\mu_p\left(\frac{b(p+1)}{2}\right)-\mu_p\left(\frac{p+1}{2}\right)=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2b(\frac{p+1}{2})k}{p}}\right\rfloor-\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2(\frac{p+1}{2})k}{p}}\right\rfloor\\=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{b(p+1)k}{p}}\right\rfloor-\left\lfloor{\frac{(p+1)k}{p}}\right\rfloor=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\left(1+\frac{1}{p}\right)bk}\right\rfloor-\left\lfloor{\left(1+\frac{1}{p}\right)k}\right\rfloor\\=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{bk+\frac{bk}{p}}\right\rfloor-\left\lfloor{k+\frac{k}{p}}\right\rfloor=\sum_{k=1}^{\frac{p-1}{2}}bk+\left\lfloor{\frac{bk}{p}}\right\rfloor-k=\sum_{k=1}^{\frac{p-1}{2}}k(b-1)+\left\lfloor{\frac{bk}{p}}\right\rfloor\\=\sum_{k=1}^{\frac{p-1}{2}}k(b-1)+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{bk}{p}}\right\rfloor=(b-1)\frac{(\frac{p-1}{2})(\frac{p-1}{2}+1)}{2}+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{bk}{p}}\right\rfloor\\=(b-1)\frac{p^2-1}{8}+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{bk}{p}}\right\rfloor$$

Which by our previous congruence modulo $2$ means:

$$\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2bk}{p}}\right\rfloor=\mu_p(b)\equiv \mu_p\left(\frac{b(p+1)}{2}\right)-\mu_p\left(\frac{p+1}{2}\right)=(b-1)\frac{p^2-1}{8}+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{bk}{p}}\right\rfloor\text{ mod } 2$$

So that we have:

$$\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2bk}{p}}\right\rfloor\equiv (b-1)\frac{p^2-1}{8}+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{bk}{p}}\right\rfloor\text{ mod } 2$$

Now if $b=a$ is an odd integer then $(b-1)\equiv (a-1)\equiv 0 \text{ mod } 2$ thus by the above equality:

$$\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2ak}{p}}\right\rfloor\equiv\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{ak}{p}}\right\rfloor\text{ mod } 2$$