Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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

share|improve this answer
    
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 1: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 1: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 1:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.