1

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

skan
  • 391

1 Answers1

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$.

bzprules
  • 1,210
  • Oh, thanks, I didn't notice that I wrote (mod p). How would you solve it if it were (mod N), with N being any integer positive number? – skan Dec 17 '12 at 01:01
  • That's actually what I've calculated, though I was using the same notation as you were. Just inspect the parity of the exponent, which is all that matters, since $N-1$ (if we're changing notation) is equivalent to $-1 \mod N$. – bzprules Dec 17 '12 at 01:24
  • For example how much is ...? $8^{7^{6^{5^{4^{3^{2}}}}}} \mod 17$ – skan Dec 17 '12 at 13:14
  • Or something maybe easier,

    $a \uparrow \uparrow b \mod c $ such as $7^{7^{7^{7^{7^{7^{7}}}}}} \mod 17$

     – skan Dec 17 '12 at 15:53
  • 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$ – skan Dec 18 '12 at 01:28