Euler's Theorem

Euler's Theorem states that for any integer a and n such that gcd(a, n) = 1, it holds that: a^φ(n) ≡ 1 (mod n)

Here, φ(n) is Euler's totient function, which counts the number of integers up to n that are coprime with n.

Algorithm

1. Calculate φ(n) using the prime factorization method.
2. Use modular exponentiation to compute a^k mod n, reducing the exponent modulo φ(n).

Time and Memory Complexity

• Euler's Totient Function: O(√n)
• Modular Exponentiation: O(log k)
• Memory Complexity: O(1)

Easy Problem 1: Compute a^b mod n where gcd(a, n) = 1

Problem: Compute 3¹⁰⁰ mod 7

#include <iostream>
using namespace std;

int power(int a, int b, int mod) {
    int result = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) result = (1LL * result * a) % mod;
        a = (1LL * a * a) % mod;
        b >>= 1;
    }
    return result;
}

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

int main() {
    int a = 3, b = 100, n = 7;
    int exponent = b % phi(n);
    cout << power(a, exponent, n) << endl;
    return 0;
}
    

Easy Problem 2: Find Modular Inverse

Problem: Find the modular inverse of 3 mod 11

#include <iostream>
using namespace std;

int power(int a, int b, int mod) {
    int res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (1LL * res * a) % mod;
        a = (1LL * a * a) % mod;
        b >>= 1;
    }
    return res;
}

int inverse(int a, int mod) {
    return power(a, mod - 2, mod); // Fermat's little theorem (special case of Euler)
}

int main() {
    cout << inverse(3, 11) << endl;
    return 0;
}
    

Intermediate Problem 1: Compute large exponent modulo composite number

Problem: Compute 7^1234567 mod 1000

#include <iostream>
using namespace std;

int power(int a, int b, int mod) {
    int res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = (1LL * res * a) % mod;
        a = (1LL * a * a) % mod;
        b >>= 1;
    }
    return res;
}

int phi(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;
}

int main() {
    int a = 7, b = 1234567, n = 1000;
    int exponent = b % phi(n);
    cout << power(a, exponent + phi(n), n) << endl;
    return 0;
}
    

Intermediate Problem 2: Sum of modular inverses

Problem: Given n, compute sum of all modular inverses of 1 to n modulo m

#include <iostream>
using namespace std;

int power(int a, int b, int mod) {
    int res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = (1LL * res * a) % mod;
        a = (1LL * a * a) % mod;
        b >>= 1;
    }
    return res;
}

int inverse(int a, int mod) {
    return power(a, mod - 2, mod); // if mod is prime
}

int main() {
    int n = 5, mod = 13;
    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum = (sum + inverse(i, mod)) % mod;
    cout << sum << endl;
    return 0;
}
    

Hard Problem: Large Exponent Tower mod n

Problem: Compute 3³³ mod 1000

Solution: Reduce top exponent using recursive φ(n)

#include <iostream>
using namespace std;

int phi(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;
}

int power(int a, int b, int mod) {
    int result = 1;
    a %= mod;
    while (b) {
        if (b & 1) result = (1LL * result * a) % mod;
        a = (1LL * a * a) % mod;
        b >>= 1;
    }
    return result;
}

int solve(int a, int depth, int mod) {
    if (depth == 1) return a % mod;
    int p = phi(mod);
    int exp = solve(a, depth - 1, p);
    return power(a, exp + p, mod); // ensure exponent is ≥ φ(mod)
}

int main() {
    cout << solve(3, 3, 1000) << endl;
    return 0;
}
    

Conclusion

Euler's Theorem is a powerful tool in modular arithmetic, particularly useful in cryptography, modular inverses, and efficient exponentiation.