Divisibility criteria

84 Views Asked by At

Notice that by $\mod 7$ we have $$6!\equiv -1 (\mod 7)$$ $$5!1!\equiv 1 (\mod 7)$$ $$4!2!\equiv -1 (\mod 7)$$ $$3!3!\equiv 1 (\mod 7).$$

  • Calculate $10!, 9!1!, 8!2!, 7!3!, 6!4!, 5!5!$ by $\mod11.$

  • Then, based on consideration of the foregoing, perform the appropriate theorem and prove it.

I've calculate $$10!\equiv -1 (\mod 11)$$ $$9!1!\equiv 1 (\mod 11)$$ $$8!2!\equiv -1 (\mod 11)$$ $$7!3!\equiv 1 (\mod 11)$$ $$6!4!\equiv -1 (\mod 11)$$ $$5!5!\equiv 1 (\mod 11).$$ I know Wilson's theorem $$(p-1)!\equiv -1 (\mod p)$$ and Leibniz theorem $$(p-2)!\equiv 1 (\mod p),$$ and I assume that $-1$ is for odd numbers $n$ and $1$ is for even numbers $n$ of the equation $$(p-n)!(n-1)!\equiv \pm 1 (\mod p), $$ for $n \geq 1$, but still can not prove it or find a theorem for this.

Do anyone know the theorem for this? Or can anyone help me to perform the appropriate theorem and prove it?

1

There are 1 best solutions below

3
On BEST ANSWER

Notice that, when we look at this $\mod p$, that we see \begin{align} (p-n)!(n-1)!&\equiv (p-n)!\cdot (n-1)\cdot (n-2)\cdot\cdots\cdot 2\cdot 1\\ &\equiv (-1)^{n-1}\cdot (p-n)!\cdot (-n+1)\cdot (-n+2)\cdot\cdots\cdot -2\cdot -1\\ &\equiv (-1)^{n-1}\cdot (p-n)!\cdot (p-n+1)\cdot (p-n+2)\cdot\cdots\cdot (p-2)\cdot (p-1)\\ &\equiv (-1)^{n-1}\cdot (p-1)!\\ &\equiv (-1)^{n-1}\cdot -1\\ &\equiv (-1)^n\mod p \end{align} Thus, as you noticed, $(p-n)!(n-1)!\equiv \pm 1\mod p$. Even more specific, $$(p-n)!(n-1)!\equiv (-1)^n\mod p$$ so that you know exactly when it is plus and when minus one.

Hope this helped!