# Euler's phi function

**Euler's phi (or totient) function** of a positive integer *n* is the number of integers in {1,2,3,...,*n*} which are relatively prime to *n*. This is usually denoted φ(*n*).

integer n |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

φ(n) |
1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 | 8 |

Clearly for primes *p*, φ(*p*)=*p*-1.
Since φ(*x*) is a multiplicative function, its value can be determined from its value at the prime powers:

**Theorem**- If
*p*is prime and*n*is any positive integer, then φ(*p*) is^{n}*p*^{n-1}(*p*-1).

**See Also:** EulersTheorem

Printed from the PrimePages <t5k.org> © Reginald McLean.