logoalt Hacker News

AnotherGoodNameyesterday at 8:56 PM1 replyview on HN

Fun fact with arrow notation, if you put it under a modulus it quickly converges to the same value no matter how high in exponents you go!

Eg. 2^2^2 = 2^4 mod 35 = 16

Let's go one higher

2^2^2^2 = 2^16 mod 35 = 16 too!

and once more for the record

2^2^2^2^2 = 2^65536 mod 35 = 16 as well. It'll keep giving this result no matter how high you go.

https://www.wolframalpha.com/input?i=2%5E2%5E2%5E2+mod+35 for a link of this to play with.

I could do this with any modulus and any exponent too.

2^3^3 = 2^3^3^3 = 7 mod 11 etc.

The reason is that the orders of powers are effected by the totient recursively and since totients always reduce, eventually the totient converges to 1. This is where the powers no longer matter under modulus. Eg. the totient of 35 is 12 (the effective modulo of the first order power), the totient of 12 is 2 (the effective modulo of the second order power), the totient of 2 is 1 (the effective modulo of the third order power) and so after 3 powers under mod 35 it converges.


Replies

ashivkumyesterday at 9:06 PM

I'm pretty sure there was a project Euler problem premised on this property but I can't find it at the moment.

show 1 reply