1
$\begingroup$

How can I calculate this? ${(p-1)}^{{(p-2)^{{(p-3)}^{(p-4)...}}}} (mod {.p}) $

and so on till 1. I don't know how to write it with a Knuth or Ackerman or more compact notation.

I've tried to find a pattern evaluating it with Mathematica, Pari, GMP, or Magma.

2 mod 3 = 2

3^2 mod 4 = 1

4^3^2 mod 5= 4

5^4^3^2 mod 6 = 1

6^5^4^3^2 mod 7 = 6

But the next step always produces an overflow.

7^6^5^4^3^2 mod 8 = ?? ( I guess it equals 1).

I guess there should be some workaround.

cheers

PD: I think I've found a way to solve some of these problems. I didn't find it myself but I found it on the Internet. Using ai≡aj(modm)⇔i≡j(mode). Where e is the multiplicative order, e=ordm(a), that's the smallest k that makes ak≡1(modm), And it can be used only if gcd(a,m)=1

1 Answers 1

6

If $p$ is even, then $(p-2)^{{(p-3)}^{\ldots}}$ is an even exponent, and so we have $(p-1)^{{(p-2)}^{\ldots}} \equiv (-1)^{{(p-2)}^{\dots}} \equiv 1 \mod p$. If $p$ is odd, then $(p-2)^{\ldots}$ is an odd exponent, and so $(p-1)^{{(p-2)}^{\ldots}} \equiv (-1)^{{(p-2)}^{\ldots}} \equiv -1 \mod p$.

  • 0
    I think I've found a way to solve some of these problems. I didn't find it myself but I found it on the Internet. Using $a^i \equiv a^j \pmod {m} \Leftrightarrow{} i \equiv j \pmod{e}$. Where e is the multiplicative order, $e=ord_m (a)$, that's the smallest k that makes $a^k \equiv 1 \pmod{m}$, And it can be used only if $gcd(a,m)=1$2012-12-18