RSA: why does phi(phi(n)) work?

Apparently an alternative method (to just using the extended Euclidean algo开发者_开发技巧rithm) of obtaining the exponent for deciphering is to do d = e**(phi(phi(n))-1) mod(phi(n)). Why does this work?

The general requirement for the RSA operation to function properly is that e*d = 1 mod X, where X is typically (p-1)*(q-1).

In this case, X is phi(n), e is e, and d is e^[phi(phi(n))-1] = e^[phi(X)-1].

Notice that e*d mod X is e*e^[phi(X)-1] mod X = e^phi(X) mod X.

Euler's Theorem states that a^phi(X) = 1 mod X, for any a which is relatively prime to X, thus the requirement holds.