# Euler's Phi function

Jump to navigation
Jump to search

**Euler's Phi function**, also known as the **totient function**, is a function that, for a given positive integer , calculates the number of positive integers smaller than or equal to that are relatively prime to . (Note that except when , only integers strictly smaller than are counted, because .)

## Definition[edit]

, where denotes the greatest common divisor of i and N.

## Properties[edit]

- for prime, because all numbers smaller than are relatively prime to .

- is even for all , because if is relatively prime to , so is , and they are distinct.

- It is a multiplicative function in the number-theoretic sense: whenever .

- , because among the integers from to , the integers not relatively prime to are precisely those divisible by , and there are of them. From this and multiplicativity, we can deduce a formula for in general:

- Let be the prime factorisation of . That is, the s are distinct primes and each is a positive integer. Then .

## Implementation[edit]

Although not the fastest, the following C implementation will work:

num_t totient (num_t i) { num_t res; /* Result */ num_t j; if (i==1) return 1; res=i; /* Check for divisibility by every prime number below the square root. */ /* Start with 2. */ if (i%2==0) { res-=res/2; do i/=2; while (i%2==0) ; } /* Since this doesn't use a list of primes, check every odd number. Ideally, skip past composite numbers.*/ for (j=3; j*j<=i; j+=2) { if (i%j==0) { res-=res/j; do i/=j; while (i%j==0) ; } } /* If i>1, then it's the last factor at this point. */ if (i>1) res-=res/i; /* Return the result. */ return res; }