Infinito exponenciación $n^{n^{n^{...^n}}} \equiv m \pmod q$ , encontrar m?

Question

deje $(n,q) \in \mathbb N^{*^2}$

Me preguntaba si era posible encontrar una función de $f_q$ tal forma que :

$f_q(n)=m$ donde $m$ es tal que $n^{n^{...^n}} \equiv m \mod q$

o, al menos, una manera fácil de encontrar m, donde $n^{n^{...^n}}$ denota "infinito" exponenciación, asumiendo, por supuesto, tiene un "límite" si ves lo que quiero decir (es decir, si exponentiate el tiempo suficiente, $n^{n^{n^{...^n}}} \equiv m \mod q$, m se vuelve constante. Es siempre el caso ? No sé, pero tiene que ser al menos periódico, puesto que m pertenece en algún lugar entre el $0$ $q-1$ ... por lo que ha de repetirse después de algunos exponentiations) Para hacer las cosas más fácil, vamos a considerar solamente la n para que $n^{n^{n^{...^n}}}$ tiende a $m \mod q$ constante

He hecho algunas pruebas y parece que a menudo tiene un "límite" ($m$ constante)

Por ejemplo, $f_{10}(7)=3$ desde :

$7^7 \equiv 49*49*49*7 \equiv 9*9*9*7 \equiv 81*63 \equiv 3$ mod 20

$7^{3+20k} \equiv 343*(343*343*343*7)^{2k} \equiv 3*(3*3*3*7)^{2k} \equiv 3*81^k \equiv$ 3 mod 20

Por lo $7^{7^{...^7}} \equiv 3$ mod 20, y, por supuesto, $\equiv 3$ mod 10

He hecho esto para otros números, y podría proporcionar con la prueba, pero es muy agotador proceso cuando n se hace grande y no podía encontrar ningún evidente patrón de...

Lo siento si la explicación es un poco desordenado, las matemáticas, estoy tratando de hacer no es muy convencional... y probablemente no muy útil, pero todavía estoy curioso... Si explicación adicional es necesario, voy a editar y añadir un poco de información

Muchas gracias por cualquier persona dispuesta a ayudarme a hacer frente a este no-tan-fácil problema de aritmética... Para ser honesto, creo que no hay una solución general, pero estaría muy agradecido si alguien pudiera encontrar f, incluso para un pequeño subconjunto de $N$.

Answer 1

Sí, esto siempre es posible, aunque no necesariamente trivial para probar. Vamos a empezar con el más fácil de caso: suponga $n$ $q$ son coprime. A continuación, la siguiente identidad se define a $f_q(n)$ de forma exclusiva (mod $q$): $$f_q(n)\equiv n^{f_{\phi(q)}(n)}\pmod q$$ donde $\phi(q)$ es de Euler totient función, igualando el número de enteros entre $0$ $q$ cuales son coprime a $q$. Por ejemplo, para obtener el $f_{10}(7)=3$ el uso de este, se nota que $\phi(10)=4$ $\phi(4)=2$ $\phi(2)=1$ y, a continuación, utilizar la recursividad (teniendo en cuenta que $f_1$ es definir mod $1$, por lo que puede ser elegido arbitrariamente): $$f_1(7)\equiv 0$$ $$f_2(7)\equiv 7^0\equiv 1$$ $$f_4(7)\equiv 7^1 \equiv 3$$ $$f_{10}(7)\equiv 7^3 \equiv 3$$ Puesto que la función es decreciente, la aplicación de la segunda identidad de un número finito de veces, finalmente se reduce a $q=1$. Aviso, como rugosa atado en cómo muchos exponentes que necesitamos, podemos decir $$f_{q}(n)=\underbrace{n^{n^{n^{\ldots ^{n}}}}}_{q\text{ times}}$$ pero esto es mucho más difícil para el equipo que la utilización de la relación de recurrencia.

El hecho crucial de que se usa aquí es que, para cualquier $q$ y lo suficientemente grande como $k$, lo siguiente es verdadero: $$a^k\equiv a^{k+\phi(q)}\pmod q$$ significado de exponenciación finalmente es periódica, con periodo de $\phi(q)$, por lo que conocer la potencia infinita de la torre del valor de mod $\phi(q)$ es suficiente para determinar que mod $q$. La mejor prueba de este hecho lo que sé es que los enteros coprime a $q$ tomado de mod $q$ forma un grupo bajo la multiplicación de orden $\phi(q)$ $\{a^0,a^1,a^2,\ldots,\}$ es un subgrupo de la misma manera que su orden de $k$ divide $\phi(q)$ debido a Lagrange del teorema. Esto implica $a^k=a^0$ y, por tanto,$a^{\phi(q)}=a^0$, lo que implica el resultado deseado. Uno puede darse cuenta que una cosa similar funciona al $n$ no es coprime a $q$ - exponenciación $n^x$ es todavía eventualmente periódico mod $q$. Uno puede probar, como una suelta de obligado, que si $x>\log_2(q)$$n^{x}\equiv n^{x+\phi(q)}\pmod{q}$, lo que nos permite calcular $f$ en una manera similar a como de largo como el representante elegimos de $f_{\phi(q)}(n)$ mod $\phi(q)$ es lo suficientemente grande.