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.