Search code examples
discrete-mathematicsnumber-theory

Unable to understand Euler totient function

I came through the following implementation of Euler-totient function

    int fi(int n) {          
    int result = n;          
    for(int i=2;i*i <= n;i++) {            
        if (n % i == 0) result -= result / i;            
        while (n % i == 0) n /= i;          
    }          
     if (n > 1) result -= result / n;          
     return result;        
   }

I am unable to understand the purpose of following result statements
result -= result / i;
result -= result / n;

Solution

  • The statement:

     result -= result / i;

    equals:

     result -= (result / i);

    which equals:

     quotient = result / i;
 result -= quotient;

    which equals:

     quotient = result / i;
 result = result - quotient;

    The second statement is very similar.