In number theory, a number used to satisfy the following congruency.
a^phi(b) mod b = a
Where a and b are arbitrary integers.
Phi is calculated by generating the
prime power decomposition of b, then applying the algorithm p^n = p^n-1*p-1 for each base in b.
Example:
The prime power decomposition of 100 is:
2^2*5^2
phi(100) is therefore:
2^(2-1)*(2-1)*5^(2-1)*(5-1)
= 2*5*4
= 40
Developed by
Euler as a generalization of
Fermat's little theorem, a^phi(b) mod b is very useful in
public key cryptography.