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)