# Showing Legendre's Properties

I've solved parts (a) and (b), but i don't know how to use this to solve (c)

(a) let $\ell>1$ an odd integer. Show $\displaystyle (\ell-1)!=2^{\frac{\ell-1}{2}}\left(\frac{\ell-1}{2}\right)!\left(1\cdot3\cdot...\cdot\ell-2\right)$
(b)let $\ell>1$ an odd integer. show that mod $\ell$, $$\left\{-a: 0 < a \leq \frac{\ell-1}{2} \ | \ \mbox{a is odd} \right\}\ = \ \left\{ b: \frac{\ell-1}{2} < b \leq \ell-1 \ | \ \mbox{b is even}\right\}$$ and have cardinality $\lfloor\frac{l-1}{4}\rfloor +1$ .

(c)Conclude from previous parts that if $\ell>0$ is an odd integer, then: $$(\ell-1)! \equiv 2^{\frac{\ell-1}{2}} (\ell-1)! (-1)^{\left \lfloor \frac{\ell-3}{4} \right\rfloor +1} \pmod{\ell}$$

• I think that in (c) l should be a prime odd numer instead of an odd integer... – NuKexZ Aug 14 '17 at 22:41
• it works also for composite odd integers. – Ahmad Aug 14 '17 at 23:42
• You didn't use Legendre symbol here (saying if $2 \equiv x^2 \bmod l$ with $l$ prime) – reuns Aug 15 '17 at 0:23

We know that :

(a) for $l>1$ odd integer => $(l-1)! = 2^{\frac{l-1}{2}} *(\frac{l-1}{2})!*(1*3*\cdots * l-2)$

(b) for $l>1$ odd integer => if $0 <a \leq \frac{l-1}{2}$ odd integer then for some $b$ even and $\frac{l-1}{2} < b \leq l-1$ we have that $-a=b$.

from (a) we get that $(l-1)! = 2^{\frac{l-1}{2}} *(\frac{l-1}{2})!*(1*3*\cdots * l-2)$ and from $(b)$ we get that $(1*3*5*\cdots *\frac{l-1}{2})$ if $\frac{l-1}{2}$ is odd integer and without $\frac{l-1}{2}$ if its even is equal to all even numbers bigger than $\frac{l-1}{2}$ and since the product include the odd integers that are bigger than $\frac{l-1}{2}$ then we've got the product of all integers bigger than $\frac{l-1}{2}$ till $l-1$ multiplied by $(\frac{l-1}{2})!$ we arrive at $(l-1)!$.

Now we arrive at $(l-1)!=2^{\frac{l-1}{2}} (l-1)!$ but remember that sometimes $\frac{l-1}{2}$ is even and sometimes is odd,we must multiply by $(-1)*(-1)*\cdots *(-1)$ because we shifted the smaller odd integers to bigger even integer using (b) (modulo $l$) but i left the minus sign which now i will get back to it.

When $\frac{l-1}{2}$ is even we have $-1$ to the power $\frac{l-1}{4}$ And When$\frac{l-1}{2}$ is odd we have $-1$ to the power $\frac{l+1}{4}$

Use the $\mod 4$ to deduce that one can combine them in $(-1)^{\frac{l-3}{4}}$.

Thus completing the proof.