Calculating $a^n\pmod m$ in the general case

Question

It is well known, that

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

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

So, $a^n\pmod m$ can be calculated by reducing n modulo $\phi(m)$.

But, for the tetration modulo $m$

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

I need the general case, where $a$ and $m$ need not to be coprime.

Which reduction can I use in this case ?

Is there an easier method to calculate the tetration modulo m without using the reductions modulo $m , \phi(m) , \phi(\phi(m)) ...$ ?

I tried to write a program in PARI, but I failed because reducing modulo $\phi(m)$ does not work, if a and m are not coprime.

Answer 1

The best you can say in general is $$a^k \equiv a^{k+\lambda(n)} \bmod n $$ for all $a$ (including those not co-prime to $n$) and all $k \geq \max v_p(n)$.

Here, $\lambda$ is Carmichael’s function and $v_p(n)$ is the exponent of $p$ in the prime factorization of $n$.

Answer 2

@sheldon I still do not have a proper algorithm to calculate tetrations modulo m, do you have one?

Peter,

This is the pari-gp code I have that I think works for all the cases I've tried. Using this code, I verified that the solution m=34276387, posted in a comment earlier as the smallest prime factor of $(2\uparrow\uparrow5+3\uparrow\uparrow5)$ is also a prime factor of $(2\uparrow\uparrow6+3\uparrow\uparrow6)$ and $(2\uparrow\uparrow7+3\uparrow\uparrow7)$, and also for all n>7. Powertower modular arithmetic seems to converge to a value independent of tetration height fairly quickly. This pari-gp code implements the combination of the Euler phi reduction, and the power2n binary exponentiation function for $(b\uparrow\uparrow i) \bmod m$. The key is the combination of the exit conditions, and the $\log_2(m)$ repeating pattern starting position, which I got from the answer to your other recent post. Then we know, for some integer $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$, which is stable for 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);
}