¿Un poder incluso más pequeño que Fermat ' s pequeño teorema sugiere?

Question

Así que sé los Estados pequeño Teorema de Fermat, que: que $p$ ser un número primo, que $a$ ser un número entero donde $p \nmid a$. Así $a^{p-1} \equiv 1 $ (mod $p$).
¿Pero es posible demostrar que hay algún poder más pequeño de $a$ que es congruente con $1$ así?

Si puedo encontrar un entero $k$ donde es el entero positivo más pequeño así que $a^k \equiv 1$ (mod $p$) entonces cómo puedo demostrar que $k \mid (p-1) $ como que completarían la prueba al afirmar que hay algún poder más pequeño de $p-1$.

Answer 1

Por supuesto, es posible que algunos $a$. Por ejemplo, si $a = -1$, luego tenemos a $a^2 \equiv 1 \pmod{p}$, independientemente de $p$. Para otros, $p-1$ es el menor entero positivo para el cual esto es, por ejemplo, $2$ $\mathbb{Z}_5$ o $3$$\mathbb{Z}_7$. Si este es el caso, llamamos a $a$ una raíz primitiva módulo $p$. Este es el número de la teoría de la terminología que expresan el hecho de que $\mathbb{Z}_p^\times$ es un grupo cíclico y $a$ es un generador de se (que no es necesariamente la única).

Para responder a su segunda pregunta, supongamos que el orden multiplicativo de a$a$$\mathbb{Z}_p^\times$$k < p-1$. El algoritmo de la división nos permite escribir $p-1 = qk + r$ algunos $0 \leq r < k$$q \in \mathbb{N}$. Por lo tanto, $a^{p-1} = a^{qk + r} = a^{qk}a^r = (a^k)^qa^r = 1$. Lo $(a^k)^q$? Lo que debe ser cierto de $r$?

Así que es cierto que el pedido se divida $p-1$. Sin embargo, la búsqueda de la multiplicación el orden de un elemento modulo $p$ es computacionalmente difícil**. Si al menos hemos sido bendecidos con la descomposición en factores primos de a $p-1$, tenemos a la esencia de la fuerza bruta de las posibilidades, dividiendo fuera de un determinado factor principal hasta la exponenciación ya no rinde $1$, luego de pasar a la siguiente factor principal.

---

**Este es un discreto registro de problema. No polinomio de tiempo de los algoritmos clásicos de los equipos aún no han sido descubiertos para esta tarea.

Answer 2

Para una fija $a$, es definitivamente posible. Observe que si $a=1$ $k=1$ obras. Para un poco menos trivial ejemplo, $4^4=1\pmod{17}$. Sin embargo, no es de menor potencia que funciona para todos los valores de $a$! Números que requieren un exponente de $p-1$ exactamente se llaman raíces primitivas. Se trata de un famoso teorema que para cada primo, hay al menos un privativa de la raíz (de hecho, hay varios, porque si $GCD(p,q)=1$ $g$ es una raíz primitiva (también llamado un "generador") si y sólo si $g^q$ es.

Ahora, supongamos $a^k=1\pmod{p}$. Queremos demostrar que $k|p-1$. Desde $p$ es primo, sabemos que existe una raíz primitiva, $g$. Si nos fijamos en el conjunto de $\{g,g^2,\ldots , g^{p-1}\}$ vemos que cada número en $\{1,\ldots p-1\}$ muestra precisamente la vez. Para demostrar que este es el caso, el aviso de que ya hay $p-1$ valores posibles y $p-1$ ubicaciones, cada número al menos una vez si y sólo si cada número aparece en más de una vez. WLOG deje $p>m>n>0$. Si $g^m=g^n,$$g^{m-n}=1\pmod{p}$. Pero esto contradice el hecho de que $g$ es un generador. Así, cada número aparece en más de una vez y para cada número aparece exactamente una vez. Ya que cada número aparece exactamente una vez, para algunos $m$ $g^m=a$. A continuación, $1=a^k=g^{km}$ $km=p-1$ desde $g$ es un generador. Por lo tanto $k|p-1$.

Answer 3

Allí no es.

El grupo $\mathbb{Z}/p^{*}$ es cíclico.

Vea también: raíces primitivas y la función de carmichael.