5
$\begingroup$

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

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

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.

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