Buscar

Question

Me piden que encuentre el$x$ positivo más pequeño, tal que$x \equiv 55! \pmod{61}$.

Esto invoca el teorema de Wilson donde$(p-1)! \equiv -1 \pmod p$.

Esto significa $60! \equiv -1 \pmod{61}$.

¿Pero a dónde ir desde aquí?

Answer 1

Haciendo módulo aritmético$\;61\;$ todo el tiempo:

PS

Answer 2

Usted sabe que:$$60!\equiv(55)! *(-1)(-2)(-3)(-4)(-5)\mod 61$ $ por lo tanto,$2x\equiv -120x\equiv -1 \mod 61$ solo necesita encontrar$x$

Answer 3

Tenemos $60! = 55! \times 56 \times 57 \times 58 \times 59 \times 60$. Tenemos$60! \equiv -1 \pmod{61}$ del teorema de Wilson. Por lo tanto,$$55! \equiv - 56^{-1} \times 57^{-1} \times 58^{-1} \times 59^{-1} \times 60^{-1} \pmod{61}$ $