Demostrar que para cualquier primo $P$ y para cualquier a del conjunto $S = \{1,2,3,.., P-1\}$ hay un $b$ también en $S$ para lo cual $ab \equiv 1 \pmod p$

Question

Esta pregunta estaba en un examen de mi clase de criptografía de hace un par de semanas y no he sido capaz de encontrar una buena prueba. En la pregunta se daba una pista: todos los números naturales tienen factores primos únicos.

He aquí un ejemplo que demuestra que es cierto para $P = 11$

$a = 1, b = 1, ab \equiv 1 \pmod P$

$a = 2, b = 6, ab \equiv 1 \pmod P$

$a = 3, b = 4, ab \equiv 1 \pmod P$

$a = 5, b = 9, ab \equiv 1 \pmod P$

$a = 7, b = 8, ab \equiv 1 \pmod P$

$a = 10, b = 10, ab \equiv 1 \pmod P$

los demás valores de a $(4, 6, 8, 9)$ aparecen como $b$ pero sigue funcionando.

He descubierto algunas cosas que no sé si importan.

Si $a = P-1$ entonces $b = P-1$ . $( (P-1)(P-1) \equiv 1 \pmod p )$

Answer 1

Sea $S = \{1,2, \dots, p-1\}$ Fijar $a \in S$ y considerar la función $m_a: S -> S$ que envía $k \mapsto k\cdot a \pmod p$ Afirmamos que $m_a$ es inyectiva. Obsérvese que si $m_a(k_1)=m_a(k_2)$ tenemos $a\cdot k_1 \equiv a \cdot k_2 \pmod p $ así que $a \cdot (k_1 - k_2) \equiv 0 \pmod p$ Esto significa que el producto $a \cdot (k_1 - k_2)$ es divisible por $p$ . En $p$ es primo, $a$ es coprimo de $p$ por lo que debe darse el caso de que $k_1 - k_2$ es divisible por $p$ , As $|k_1 - k_2| < p$ y $p$ es primo, sólo puede serlo si $k_1 - k_2 = 0$ Así pues $k_1 = k_2$ . Ahora finalmente como $m_a$ es una función inyectiva de un conjunto finito a sí mismo, debe darse el caso de que $m_a$ es suryectiva, lo que implica que existe alguna $b \in S$ tal que $a\cdot b \equiv 1 \pmod p$

Obsérvese que esta demostración puede simplificarse y generalizarse si se conocen algunas nociones básicas de la teoría de anillos: equivale al hecho de que un dominio integral finito es un campo.

Answer 2

Es fácil comprobar que los valores de $f(x)=ax$ son distintos para $x \in \{0,...,p-1\}$

Por lo tanto, hay un único $b$ con la propiedad $f(b)=1$ .

Answer 3

Veamos eso, toma $a$ en $S $ entonces como $p $ es primo $(a,p)=1$ . Entonces existen enteros $r,s $ tal que $ar+ps=1$ esto implica $ps=1-ar $ entonces $p| 1-ar $ y esta es la definición de $1 \equiv ar \pmod p $ y entonces la b que buscas es la r que usamos. Esto demuestra que tal b existe y dice cómo se puede encontrar. Espero que te sirva de ayuda.