# Euler's Phi function

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

## Definition

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

## Properties

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