Cómo encontrar el postive $m,n$, $a^n\equiv 1\pmod m$

Question

Encontrar todos los enteros positivos pares de $(m,n)$ $m,n \ge 2$ tal que para todo $a\in\{1,2,\cdots,n\}$, $$a^n\equiv 1\pmod m$$

Si $(a,m)=1$, el Teorema de Euler nos dice que $$a^{\phi(m)}\equiv 1\pmod m.$$ Así que una familia de soluciones de es $(n,m) = (\phi (m), m)$. Es posible describir todas las familias?

Answer 1

Una prueba basada en las raíces de $X^n-1$

Respuesta: La única pares de la satisfacción de su declaración se $(p,p-1)$ para los números primos $p$

Dado un par de enteros $(m,n)$ tal que $n>1$ supongamos que para cada $k\in\{1,\cdots,n\}$ tenemos: $$k^n\equiv 1 \mod m\tag1$$ Como notado por Barry Cipra $n$ debe ser menor que $p$ el menor divisor primo de $m$ porque $p^{n}\not\equiv 1\mod m$ por lo tanto $n<p$, Y como consecuencia de $(1)$las raíces de $x^n-1$ $\Bbb Z_p$ son exactamente $1,\cdots,n$.

Ahora vamos a probar que $n\geq p-1$, por contradicción, supongamos que $n<p-1$:

• Si $n$ es incluso, a continuación, $p-1$ es otra raíz de $x^n-1$ $\Bbb Z_p$ lo cual es absurdo.
• Si $n$ es impar, a continuación, $n+1=2a$ $a,2\leq n$ por lo tanto $n+1$ es otra raíz del polinomio ($2^n\equiv 1\mod p $$a^n\equiv 1\mod p$implica $(n+1)^n\equiv 1\mod n$) lo cual es absurdo.

Como conclusión $n=p-1$. Ahora ha dado otra prime $q$ que se divide $m$, se puede demostrar utilizando el mismo método (como hicimos para $p$ $n\geq q-1$ y debido a $n=p-1$ tenemos $p=q$. Si $m$ es divisible por $p^2$, sabemos que: $$(p-1)^{p-1}\equiv -p(p-1)+1 \mod p^2 $$ cual es absurdo, ya $(p-1)^{p-1}\equiv 1\mod m\equiv 1\mod p^2$ por lo tanto $m=p$

Finalmente, hemos demostrado que la $n=p-1$ $m=p$ es aprime

Answer 2

Esta es sólo una respuesta parcial, principalmente en la forma de un par de evidente observaciones.

Primero de todos, con el fin de tener $a^n\equiv1$ mod $m$ para todos los $a\in\{1,2,\ldots,n\}$, $n$ debe ser menor que el menor divisor primo de $m$, ya que no puede tener $p^n\equiv1$ mod $m$ si $p\mid m$.

Segundo, el más obvio de la familia de soluciones es $(m,n)=(p,p-1)$ (impar) de los números primos $p$. Esto es sólo Fermat Poco Teorema. No generalizar a $(m,\phi(m))$, ya que el $\phi(m)$ en general es mayor que el menor divisor primo de $m$.

Me inclino a pensar que no hay otras soluciones, pero no tengo una prueba. Si alguien puede pensar en uno, o pueden producir una solución (o familia de soluciones) con nonprime $m$'s, por favor, publicarlo como una respuesta!

Answer 3

Usted está buscando algo que se llama el "orden" de un elemento perteneciente al conjunto de los enteros modulo m. Ahora, este término proviene del álgebra abstracta, como la orden de un elemento en un grupo (no se preocupe acerca de los axiomas por ser un grupo, solo se sabe que el conjunto de los residuos mod m es un grupo) es el exponente $k$ tal que $a^k = e$.

Ahora, $e$ denota el elemento de identidad de un grupo en alguna operación. En nuestro caso, este es el elemento de identidad de los enteros bajo la multiplicación. Esto es bastante evidentemente, se considera que 1. Por lo tanto, el orden de algún elemento modulo m es el número entero $k$ tal que $$a^k \equiv 1 (\bmod m)$$ Now, as you probably know, a is restricted to being a member of the reduced residue set modulo m, as in, any integer such that $(a,m)=1$. Thus, for $$, we have $\phi (m)$ choices for a. Now, the integer $un$ such that $$a^{\phi (m)} \equiv 1 (\bmod m)$$ is known as a primitive root in number theory, or, a generator of the cyclic group of reduced residues modulo m in abstract algebra. So, you have the primitive roots, and then you have the elements of order $k <\phi (m)$. An element cannot have an order greater than $\phi (m)$.

Algo a tener en cuenta es que el orden de un elemento debe dividir $\phi (m)$. Esto puede ser fácilmente comprobado mediante el algoritmo de la división para $\phi (m)$, la reescritura es $kq+r$, y mostrando que el $r=0$.

Otro importante teorema afirma que para cualquier $prime$ módulo, la cantidad de raíces primitivas mod m $\phi (p-1)$ donde $p$ es primo. Esto puede ayudar a reducir el resto de la coprime elementos. También, para comprobar el orden de los elementos, ya que sabe que la orden debe dividir su phi función, sólo es necesario la verificación de los poderes, que son divisores de $\phi (n)$, que es significativamente más rápido.

No voy a demostrar que (a menos que usted realmente quiere..), pero hay dos teoremas que son bastante útiles para los módulos de ciertas formas. En primer lugar, para cualquier extraño $a$, $$a^{\phi (2^{\alpha})/2} \equiv 1 (\bmod 2^{\alpha})$$

Y luego también tenemos un teorema de la afirmación de que una raíz primitiva existe si y sólo si $m = 1, 2, 4, p^{\alpha}$ o $2p^{\alpha}$, donde m es el módulo.

Ahora, no estoy seguro exactamente lo que usted entiende por familias, pero puedo decir que el orden de cualquier elemento de módulo m se divide $\phi (m)$, por lo que las familias estarían todos los elementos que tienen una orden de un divisor de a $\phi (m)$.