# Euler's Phi function

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

## Definition

$\phi (N)={\Big |}\,\{i~~|~~1\leq i\leq N~\land ~\gcd(i,N)=1\}{\Big |}$ , where $\gcd(i,N)$ denotes the greatest common divisor of i and N.

## Properties

• $\phi (p)=p-1$ for $p$ prime, because all numbers smaller than $p$ are relatively prime to $p$ .
• $\phi (N)$ is even for all $N>2$ , because if $k$ is relatively prime to $N$ , so is $N-k$ , and they are distinct.
• It is a multiplicative function in the number-theoretic sense: $\phi (MN)=\phi (M)\phi (N)$ whenever $\gcd(M,N)=1$ .
• $\phi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right)$ , because among the integers from $1$ to $p^{k}$ , the integers not relatively prime to $p^{k}$ are precisely those divisible by $p$ , and there are $p^{k-1}$ of them. From this and multiplicativity, we can deduce a formula for $\phi (N)$ in general:
• Let $N=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{r}^{\alpha _{r}}$ be the prime factorisation of $N$ . That is, the $p_{i}$ s are distinct primes and each $\alpha _{i}$ is a positive integer. Then $\phi (N)=(p_{1}^{\alpha _{1}}-p_{1}^{\alpha _{1}-1})\cdots (p_{r}^{\alpha _{r}}-p_{r}^{\alpha _{r}-1})=N\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)$ .

## Implementation

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. */
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;
}