Tengo el "ejercicio de Calcular el $10! \pmod{13}$".
Tengo los dos métodos siguientes para resolver el ejercicio:
- Aproximación de fuerza bruta
$$ 1! \equiv 1 \pmod{13} \\ 2! = 2 \cdot 1! \equiv 2 \cdot 1 \equiv 2 \pmod{13} \\ 3! = 3 \cdot 2! \equiv 3 \cdot 2 \equiv 6 \pmod{13} \\ \cdots \\ 10! = 10 \cdot 9! \equiv 10 \cdot 11 = 110 = 8 \cdot 13 + 6 \equiv 6 \pmod{13} $$
- Enfoque el uso del teorema de Wilson:
Wilson del teorema de los estados que $$p \in \mathbb{P} \implies (p-1)! \equiv -1 \pmod p$$
Para mi ejercicio: $$13 \in \mathbb{P} \implica \\ (13-1)! = 12! = 10!\cdot 11 \cdot 12 \equiv -1 \pmod{13} \implica \\ 10! \equiv -(11 \cdot 12)^{-1} \pmod{13} $$ El uso de Fermat poco teorema de $$ a^p \equiv \pmod p \implica un^{p-2} \cdot a \cdot a \equiv a^{-1} \cdot a \cdot a \pmod p \implica un^{p-2} \equiv a^{-1} \pmod p \\ $$ Para mi ejercicio: $De$10! = -(11 \cdot 12)^{-1} \equiv \\ -(11 \cdot 12)^{13-2} = -(11 \cdot 12)^{11} \equiv \\ -(-2 \cdot -1)^{11} = -2^{11} = \\ -2^6 \cdot 2^5 \equiv 1 \cdot 2^5 = \\ 32 \equiv 6 \pmod{13} \\ $$
Ambos enfoques se ven muy voluminosos.
En el primer método que tengo que hacer la $O(n)$ multiplicaciones.
En el segundo método que tengo que hacer la $O(p-n)$ multiplicaciones que es menor que en el primer método, pero también puede ser enorme número de grandes $p$$n$.
Hay una manera para mejorar mi solución?
Es allí una manera eficiente para calcular el $n! \pmod p$ grande $n$$p$?
