AntInLoop

Euler's Totient Function & Euler's Theorem Code Implementations

Complete Euler's Totient Function & Euler's Theorem code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Euler's Totient Function & Euler's Theorem Guide · Launch Interactive Visualizer

C++ Implementation

// Euler's Theorem in C++

class Euler {
public:
    // Compute Euler's Totient Function φ(n)
    static int totient(int n) {
        int result = n;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        }
        if (n > 1)
            result -= result / n;
        return result;
    }

    // Fast exponentiation
    static long long modPow(long long a, long long b, long long mod) {
        long long result = 1;
        a %= mod;
        while (b > 0) {
            if (b % 2 == 1)
                result = (result * a) % mod;
            a = (a * a) % mod;
            b /= 2;
        }
        return result;
    }

    // Modular inverse using Euler’s Theorem
    static long long modInverseEuler(long long a, long long n) {
        return modPow(a, totient(n) - 1, n);
    }
};

JAVA Implementation

// Euler's Theorem in Java

public class Euler {

    // Euler's Totient Function φ(n)
    public static int totient(int n) {
        int result = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0) n /= i;
                result -= result / i;
            }
        }
        if (n > 1) result -= result / n;
        return result;
    }

    // Fast exponentiation
    public static long modPow(long a, long b, long mod) {
        long result = 1;
        a %= mod;
        while (b > 0) {
            if ((b & 1) == 1) result = (result * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return result;
    }

    // Modular inverse using Euler's Theorem (if a and n are coprime)
    public static long modInverseEuler(long a, long n) {
        return modPow(a, totient((int) n) - 1, n);
    }
}

JAVASCRIPT Implementation

// Euler's Theorem in JavaScript

// Compute Euler's Totient Function (φ(n))
function totient(n) {
  let result = n;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) {
      while (n % i === 0) n /= i;
      result -= result / i;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}

// Fast exponentiation: a^b % mod
function modPow(a, b, mod) {
  let result = 1;
  a %= mod;
  while (b > 0) {
    if (b % 2 === 1) result = (result * a) % mod;
    a = (a * a) % mod;
    b = Math.floor(b / 2);
  }
  return result;
}

// Modular inverse using Euler's Theorem (if gcd(a, n) == 1)
function modInverseEuler(a, n) {
  return modPow(a, totient(n) - 1, n);
}

PYTHON Implementation

# Euler's Theorem in Python

# Euler's Totient Function φ(n)
def totient(n):
    result = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
        i += 1
    if n > 1:
        result -= result // n
    return result

# Fast exponentiation
def mod_pow(a, b, mod):
    result = 1
    a %= mod
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % mod
        a = (a * a) % mod
        b //= 2
    return result

# Modular inverse using Euler’s Theorem (when gcd(a, n) == 1)
def mod_inverse_euler(a, n):
    return mod_pow(a, totient(n) - 1, n)