Carmichael Function - Numeric Example

Numeric Example

52 ≡ 1 (mod 6) because 5 and 6 are coprime. In other words, gcd(5,6)=1. Here we had to raise 5 to the 2nd power because the Carmichael function of 6 is 2. Recall that 1 and 5 are the only two numbers smaller than 6 that are relatively prime to 6.

However, 32 = 9 ≡ 3 (mod 6) obviously doesn't work because the number 3 is impermissible as a base to be raised to the 2nd power. We know that gcd(3,6)=3, not 1.