Again irreducible (Editorial)

The number of regular irreducible fractions $p/n$ (with denominator $n$) is equal to the number of positive integers $p$ such that p < n and $p$ is coprime with $n$. The count of such numbers $p$ equals the Euler function $\phi (n)$.

Consider the set of all proper fractions with denominator $12$:

After reducing the fractions to their lowest terms, we obtain:

Now, let us group these fractions according to their denominators:

Among these denominators, every divisor $d$ of $12$ occurs, together with all $\varphi (d)$ numerators that are relatively prime to $d$. In other words, for each divisor $d$ of $12$, there are exactly $\varphi (d)$ irreducible fractions with denominator $d$.

Since every fraction from the original set appears exactly once after reduction, we have:

More generally, if we start with the sequence of proper fractions

and reduce each fraction to its lowest terms, we obtain the following identity:

Example

For n = 12 we have \varphi(12) = 4 regular irreducible fractions:

Algorithm implementation

The euler function computes the value of $\phi (n)$.

int euler(int n)
{
  int i, result = n;
  for (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;
}

The main part of the program. Read the input value of $n$ and print $\phi (n)$.

while(scanf("%d",&n),n)
  printf("%d\n",euler(n));

Java implementation

import java.util.Scanner;

public class Main
{
  static int euler(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;
  }
    
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      int n = con.nextInt();
      if (n == 0) break;
      System.out.println(euler(n));
    }
    con.close();
  }
}

Python implementation

import math

The euler function computes the value of $\phi (n)$.

def euler(n):
  result = n
  i = 2
  while i <= math.isqrt(n):
    if n % i == 0:
      result -= result // i
      while n % i == 0: n //= i
    i += 1
  if n > 1: result -= result // n
  return result

The main part of the program. Read the input value of $n$ and print $\phi (n)$.

while True:
  n = int(input())
  if n == 0: break
  print(euler(n))