The Euler's totient function, or phi (φ) function is a very
important number theoretic function having a deep relationship to prime
numbers and the so-called order of integers. The totient
φ(*n*) of a positive integer *n*
greater than 1 is defined to be the number of positive integers less
than *n* that are coprime to *n*.
φ(*1*) is defined to be 1. The following table shows
the function values for the first several natural numbers:

n | φ(n) | numbers coprime to n |
---|---|---|

1 | 1 | 1 |

2 | 1 | 1 |

3 | 2 | 1, 2 |

4 | 2 | 1,3 |

5 | 4 | 1,2,3,4 |

6 | 2 | 1,5 |

7 | 6 | 1,2,3,4,5,6 |

8 | 4 | 1,3,5,7 |

9 | 6 | 1,2,4,5,7,8 |

10 | 4 | 1,3,7,9 |

11 | 10 | 1,2,3,4,5,6,7,8,9,10 |

12 | 4 | 1,5,7,11 |

13 | 12 | 1,2,3,4,5,6,7,8,9,10,11,12 |

14 | 6 | 1,3,5,9,11,13 |

15 | 8 | 1,2,4,7,8,11,13,14 |

Can you find some relationships between *n* and
φ(*n*)? One thing you may have noticed is
that:

when(e.g. 2, 3, 5, 7, 11, 13),nis a prime numberφ(.n) =n-1

But how about the composite numbers? You may also have noticed
that, for example, 15 = 3*5 and φ(*15*) =
φ(*3*)*φ(*5*) = 2*4 = 8. This is
also true for 14,12,10 and 6. However, it does not hold for 4, 8, 9. For
example, 9 = 3*3 , but φ(*9*) = 6 ≠
φ(3)*φ(*3*) = 2*2 =4. In fact, this multiplicative
relationship is conditional:

when.andmnare coprime, φ(m*n) = φ(m)*φ(n)

The general formula to compute φ(n) is the following:

I

f the prime factorisation of n is given by n =p._{1}^{e1}*...*p_{n}^{en}, then φ(n) = n *(1 - 1/p_{1})* ... (1 - 1/p_{n})

For example:

9 = 3

^{2}, φ(*9*) = 9* (1-1/3) = 64 =2

^{2}, φ(*4*) = 4* (1-1/2) = 215 = 3*5, φ(

*15*) = 15* (1-1/3)*(1-1/5) = 15*(2/3)*(4/5) =8

Euler’s theorem generalises Fermat’s theorem to the case where the modulus is not prime. It says that:

if

nis a positive integer and a, n are coprime, thena^{φ(n)}≡ 1 modnwhere φ(n) is the Euler's totient function.

Let's see some examples:

165 = 15*11, φ(165) = φ(15)*φ(11) = 80. 8

^{80}≡ 1 mod 1651716 = 11*12*13, φ(1716) = φ(11)*φ(12)*φ(13) = 480. 7

^{480}≡ 1 mod 1716φ(13) = 12, 9

^{12}≡ 1 mod 13

We can see that Fermat's little theorem is a special case of
Euler's Theorem: for any prime *n*, φ(n) =
*n*-1 and any number a 0< a <n is coprime to
*n*. From Euler's Theorem, we can easily get several
useful corollaries. First:

if

nis a positive integer anda, nare coprime, thena^{φ(n)+1}≡ a modn.

This is because
*a*^{φ(n)+1} =
*a*^{φ(n)}*a,
*a*^{φ(n)} ≡ 1 mod
*n* and *a ≡ a *mod
*n*, so
*a*^{φ(n)+1} ≡
*a* mod *n*. From here, we can go
even further:

if

nis a positive integer anda, nare coprime, b ≡ 1 mod φ(n), thena^{b}≡amodn.

If b ≡ 1 mod φ(n), then it can be written as *b =
k*φ(n)*+1 for some *k*. Then
*a*^{b} =
a^{k*φ(n)+1} =
(a^{φ(n)})^{k}*a. Since
*a*^{φ(n)} ≡ 1 mod
*n*,
(*a*^{φ(n)})^{k}
≡ 1^{k} ≡ 1 mod *n*. Then
(a^{φ(n)})^{k}*a ≡
*a* mod *n. *This is why RSA
works.

**Useful Links**