Cálculo de$a^n\pmod m$ en el caso general

Question

Es bien sabido, que

$$a^{\phi(m)}\equiv1\pmod m ,$$

si $\gcd(a,m)=1.$

Por eso, $a^n\pmod m$ puede ser calculado mediante la reducción de modulo n $\phi(m)$.

Pero, para el tetration modulo $m$

$$a \uparrow \uparrow n\pmod{m},$$

Necesito el caso general, donde $a$ $m$ no necesita ser coprime.

Que la reducción puedo usar en este caso ?

Hay un método más sencillo para calcular el tetration modulo m sin el uso de las reducciones modulo $m , \phi(m) , \phi(\phi(m)) ...$ ?

Traté de escribir un programa en PARI, pero no pude ya que la reducción del modulo $\phi(m)$ no funciona, si a y m no son coprime.

Answer 1

@sheldon yo todavía no tienes un buen algoritmo para calcular tetrations modulo m, ¿tienes uno?

Pedro,

Este es el pari-gp código que tengo que creo que funciona para todos los casos que he probado. El uso de este código, he comprobado que la solución m=34276387, publicado en un comentario anterior como el menor factor primo de $(2\uparrow\uparrow5+3\uparrow\uparrow5)$ es también un factor principal de $(2\uparrow\uparrow6+3\uparrow\uparrow6)$$(2\uparrow\uparrow7+3\uparrow\uparrow7)$, y también para todo n>7. Powertower aritmética modular parece converger a un valor independiente de tetration altura con bastante rapidez. Este pari-gp código implementa la combinación de la phi de Euler de la reducción, y la power2n exponenciación binaria función de $(b\uparrow\uparrow i) \bmod m$. La clave es la combinación de las condiciones de salida, y el $\log_2(m)$ patrón que se repite en la posición de partida, que me de la respuesta a tu otro post reciente. Entonces sabemos que, para algún entero $k \lt \log_2(m)$,

$$b^{k} \equiv b^{ k+\phi(m)} \pmod m$$

This reduces the problem to $b^z \equiv (b\uparrow\uparrow i) \pmod m$ where $z=(b\uparrow\uparrow (i-1)) \bmod \phi(m)$, so long as $\log_2(m)<z<b\uparrow\uparrow i$. This requires more work; it would be nice to prove that the exit conditions identified in the pari-gp code are sufficient but for now, working pari-gp code will have to do. Code update, I generalized the boundary condition for $((b\uparrow\uparrow i) \bmod m)$ where m is a multiple with n>=2, $n(b\uparrow\uparrow i)$, which is a boundary condition for the math equations. This is fixed in the pari-gp code.

The repeating patterns can be shorter then $\phi(m)$, but that isn't required. I have another much slower pari-gp program that brute force finds the shortest chains, and the final results match with this version. Let me know if you find any bugs or missing boundary conditions. I have tested it fairly exhaustively against the power2n code for prime values of p, with the power tower height=4, and against the slower version for other heights, and for non-prime values of p.

The code can do other interesting stuff, like calculate an arbitrary number of right hand digits of Graham's number, $(3\uparrow\uparrow 13) \bmod 10^{12}=262464195387$, que es estable para i>13.

/* calculates (b^^i) mod m */
reducetower(b,m,i) = {
  local(n,rz,log2p);
  /* these are the recursion exit conditions */
  if ((b%m)==0, return(0));             /* "0" if b divisible by m, or m=1  */
  if ((i==2), return(power2n(b,m,b)));  /* if i==2, calculate  (b^b) mod m  */
  /* boundary cases for m=3n*(3^^3), just detect m>3^^3, similary for 2^^4  */
  /* and similarily for m=2n*(2^^3), just detect m>2^^3                     */
  if ((b==2) && (i==3) && (m>16),            return (16));
  if ((b==2) && (i==4) && (m>65536),         return (65536));
  if ((b==3) && (i==3) && (m>7625597484987), return (7625597484987));
  /* theoretically, there is also (b==4) && (i==3) && (m>4^^3)              */

  log2p=0;
  n=eulerphi(m); /* n replaces m in recursion, reducetower(b,n,i-1); */
  if (n+1<m, /* if m is not a prime */
    log2p=floor(log(m)/log(2)); /* repeating pattern length n guarenteed    */
  );
  rz = reducetower(b,n,i-1);  /* recursion with i-1, and n replacing m      */
  /*  we know there are repeats beginning at or before log2p, so that       */
  /*  b^log2p = b^(log2p+n)                                                 */
  /*  b^b^z can be replaed with b^(b^z mod n) as long as (b^z mod n)>log2p  */
  /*  if b^z<log2p, keep adding (b^z)+n until >= log2p                      */
  while ((log2p>0) && (rz<log2p), rz=rz+n);
  rz = power2n(b,m,rz);  /*  (b^rz) mod m  */
  if (debugprint,
    print("("b"^^"i")%"m"=("b"^(("b"^^"i-1")%"n"))%"m"="rz);
  );
  return(rz);
}
power2n(z,m,i) = {
  local(t,y);
  if (i==0,return(1));
  y=z;
  t=1;
  /* express i in base 2, multiply the subparts of i as they are calculated */
  while ((y<>1) && (i>0),
    if ((i%2)==1, t=(t*y)%m;i=i-1);
    y=(y*y)%m;
    i=i/2;
  );
  return(t);
}

Answer 2

Lo mejor que puedes decir en general es$$a^k \equiv a^{k+\lambda(n)} \bmod n $ $ para todos los$a$ (incluidos aquellos que no son primarios de$n$) y todos los$k \geq \max v_p(n)$.

Aquí,$\lambda$ es la función de Carmichael y$v_p(n)$ es el exponente de$p$ en la factorización prima de$n$.