Cuando se $a^k \pmod{m}$ periódico de la secuencia?

Question

Deje $a$ $m$ ser enteros positivos con $a < m$. Supongamos que $p$ $q$ son primos divisores de $m$. Supongamos que $a$ es divisible por $p$ pero no $q$.

Es necesariamente un entero $k>1$ tal que $a^k \equiv a \pmod{m}$?

O es que lo mejor que podemos hacer es decir que hay un $n>0$ $k>1$ tal que $a^{n+k} \equiv a^n \pmod{m}$

¿Qué se puede decir acerca de la $n$$k$?

EDIT: Corregido para tener $k>1$ en lugar de $k>0$.

EDIT: El siguiente documento de respuestas a mis preguntas acerca de $n$ $k$ muy bien.
A. E. Livingston y M. L. Livingston, de La congruencia $a^{r+s} \equiv a^r \pmod{m}$, Amer. De matemáticas. Mensual $\textbf{85}$ (1978), no.2, 97-100.
Es una de las referencias en el papel de las Matemáticas Gemas citado. Arturo parece decir esencialmente lo mismo en su respuesta.

Answer 1

Seguro que hay, vamos a $k=1$.

Si la pregunta es reformulado, a $k>1$, entonces la respuesta es no, vamos a $a=2$$m=12$.

Para obtener más general de trabajo a lo largo de estas líneas, buscar "menos universal exponente" o "Carmichael función." Este es el mínimo número de $\lambda(m)$ tal que $a^{\lambda(m)}\equiv 1 \pmod{m}$ todos los $a$ relativamente primer a $m$.

Podemos encontrar una $k$ tal que $a^{\lambda(m)+k}\equiv a^k \pmod{m}$ por cada $a$. Esto es automáticamente si $a$ $m$ son relativamente primos. Para cuidar de los no primos relativos de los casos, todo lo que tenemos que hacer es asegurarnos de que por cualquier prime $p$ que divide tanto a a $a$ y $m$, $a^k \equiv 0 \pmod{m}$. Para asegurarse de esto, vamos a $k$ ser el mayor exponente que se produce en el primer poder de la factorización de $m$.

Answer 2

Una buena presentación de tales semigroup generalizaciones de Euler-Fermat y teorema relacionados con la teoría de números es la siguiente libremente disponible en papel

S. Schwarz, El papel de semigroups en la teoría elemental de números, las Matemáticas. Slovaca, Vol. 31 (1981) pp 369-395.

Answer 3

(Suponiendo que significaba $k\gt 1$)

La mejor que se puede decir decir es que hay $n$ $k$ tal que $a^{n+k}\equiv a^n\pmod{m}$. Y, por supuesto, hay un mínimo de $n$ para los que no existen tales $k$, y un mínimo de $k$ que hacen de esta verdad; en el sentido de que si $r$ $s$ son cualquier enteros positivos tales que a$a^r\equiv a^s\pmod{m}$,$r,s\geq n$, e $r\equiv s\pmod{k}$. (Estos son los "cíclico monoids/semigroups".)

Por ejemplo, $m=12$, $a=2$. Entonces $a^2\equiv 4\pmod{12}$, $a^3\equiv 8\pmod{12}$, $a^4\equiv 4\pmod{2}$, y usted nunca volver a $2$.

El problema surge cuando usted tiene un prime $p$ que divide tanto a a$a$$m$, pero el mayor poder de $p$ que divide $a$ es estrictamente menor que el mayor poder de $p$ que divide $m$.

Considere la situación de un primer a un tiempo. Si $\gcd(p,a)=1$, entonces no es un $k_p$ tal que $a^{k_p}\equiv a\pmod{p^{r_p}}$ donde $p^{r_m}$ es la potencia exacta de $p$ que divide $m$. Sabemos que $k_p$ divide $p^{r_p-1}(p-1)$, pero en general no sabemos más que eso.

Si $p|a$, vamos a $p^{s_p}$ ser la potencia exacta de $p$ que divide $a$. Si $n_p=\lceil \frac{r_p}{s_p}\rceil$ tenemos que $n_p$ es el menor entero positivo tal que $a^{n_p+1}\equiv a_{n_p}\pmod{p^{r_p}}$, y además, $a$, $a^2,\ldots,a^{n_p}$ son pares distintos modulo $p^{r_p}$.

Por el Teorema del Resto Chino, $a^{n+k}\equiv a^n\pmod{m}$ si y sólo si $a^{n+k}\equiv a^n\pmod{p^{r_p}}$ para cada uno de los prime $p$ que divide $m$. Para los números primos que no se dividen $a$, esto implica que $k$ es un múltiplo de a $k_p$; la de los números primos que hacer dividen $a$, esto implica que $n\geq n_p$ $k$ es arbitrario.

Así que se puede decir que el $n\geq \max\{n_p \mid p|\gcd(a,m)\}$ $\mathrm{lcm}\{k_p\mid p\text{ divides }m\text{ and }p\text{ does not divide }a\}$ divide $k$.

Por el contrario, si $n$ $k$ satisfacer esas condiciones, entonces el valor de $n$ garantiza que $a^{n+k}\equiv a^n\pmod{p^{r_p}}$ para todos los primos que dividen a $\gcd(a,m)$; y el valor de $k$ garantiza que $a^{n+k}\equiv a^n\pmod{p^{r_p}}$ para todos los primos que dividen a $m$ pero no $a$.

Answer 4

Esto está relacionado con una cuestión de la mina, es decir, A lo divisores $a$ $n$ puede el Teorema de Euler multiplicado por $a$ ser generalizado, es decir, cuando es $a^{\phi(n)+1}\equiv a \pmod n$? y una respuesta es que el $a^k$ $m=\gcd(a,n)$ debe ser coprime, donde $k=\phi(n)/\phi(m)$.

En su caso, $n=pq$ $p\neq q$ primos y $\gcd(a,n)=p=m$, por lo $k=\frac{\phi(pq)}{\phi(p)}=\frac{(p-1)(q-1)}{p-1} = q-1$, es decir,

$a^{q-1}\equiv a\pmod{pq}$ $\gcd(a,pq)=p$ fib $a^{q-1}$ $p$ son coprime o $a\equiv0\pmod{pq}$. Desde $p$ divide $a$, la ex no puede ser el caso y, por tanto, la única solución posible es $a\equiv0\pmod{pq}$, que sin embargo significa $a$ se divide también por $q$, lo que contradice su suposición. Por lo tanto, la respuesta a la pregunta es "No".