∑MathIntermediate

Euler's Theorem

Key Points

•
Euler’s Theorem says that if a and n are coprime, then a raised to the power $φ (n)$ is congruent to 1 modulo n.
•
It generalizes Fermat’s Little Theorem by replacing p−1 with $φ (n)$ for composite moduli n.
•
Use it to shrink huge exponents: when gcd(a,n)=1, reduce b modulo $φ (n)$ before computing $a^{b}$ mod n.
•
Be careful: if gcd(a,n)≠1, you cannot blindly reduce the exponent; use case analysis (e.g., CRT) or skip reduction.
•
$φ (n)$ can be computed by prime factorization using $φ (n) = n \prod_{p ∣ n}$ (1−1/p).
•
Binary exponentiation computes $a^{b}$ mod n in O(log b) time, and Euler’s Theorem can reduce b first.
•
For even stronger reduction, the Carmichael function $λ (n)$ can replace $φ (n)$ because it is the exponent of the multiplicative group.
•
Euler’s Theorem underlies modular inverses mod n (when gcd(a,n)=1) and is central in RSA (ed≡1 mod $φ (n)) .$

Prerequisites

→Modular arithmetic (congruences) — Understanding what a≡b (mod n) means is foundational for interpreting Euler’s Theorem.
→Greatest common divisor (gcd) and Euclid’s algorithm — Coprimality is required by Euler’s Theorem and for modular inverses.
→Prime factorization — Computing φ(n) or λ(n) needs the prime factorization of n.
→Binary exponentiation (fast power) — Efficiently computes a^b mod n once the exponent has been reduced.
→Chinese Remainder Theorem (CRT) — When gcd(a,n)≠1, solving modulo prime powers then recombining with CRT is a robust approach.

Detailed Explanation

Tap terms for definitions

01Overview

Euler’s Theorem is a cornerstone of modular arithmetic. It states that for any integer a that is coprime to n (their greatest common divisor is 1), raising a to the Euler totient of n, denoted φ(n), yields 1 modulo n. In symbols: a^{φ(n)} ≡ 1 (mod n) when gcd(a,n)=1. This generalizes Fermat’s Little Theorem, which is a special case for prime moduli where φ(p)=p−1. Practically, Euler’s Theorem is a tool for taming huge exponents in modular computations. If you need a^b mod n and gcd(a,n)=1, you can reduce b modulo φ(n) because the powers of a cycle with period dividing φ(n). This makes problems that seem impossible—like raising numbers to exponents with thousands of digits—computationally manageable when we can compute φ(n) and ensure the coprimality condition. Computationally, φ(n) can be found from the prime factorization of n using φ(n)=n∏_{p|n}(1−1/p). With φ(n) and fast binary exponentiation, modular exponentiation becomes efficient. Euler’s Theorem also provides a way to compute modular inverses modulo composite n (again requiring gcd(a,n)=1), which is key in cryptography (e.g., RSA). However, care is necessary: if a and n are not coprime, the theorem does not apply directly and other tools (like Chinese Remainder Theorem) or case-by-case reasoning are needed.

02Intuition & Analogies

Think of modular arithmetic like a clock. On a 12-hour clock, repeatedly adding 5 hours cycles through specific times. The behavior eventually repeats. In the same way, when you multiply by a repeatedly modulo n (i.e., consider a, a^2, a^3, … mod n), you move around a “multiplicative clock.” If a and n are coprime, you’re guaranteed to stay on the set of residues that also have inverses (the “units”), which forms a closed loop under multiplication. Euler’s totient φ(n) counts how many positions are on this multiplicative clock—the number of residues between 1 and n that are coprime to n. If you start at 1 and multiply by a, then again by a, and so on, you must eventually return to 1 because you’re walking around a finite loop. The loop length is called the multiplicative order of a modulo n. Although this loop could be shorter, it must divide the total number of positions, φ(n). That means after φ(n) steps (or some divisor of it), you complete a full cycle and land back at 1: that’s a^{φ(n)} ≡ 1 (mod n). If this is a loop, big exponents are like counting very far along the circle. You can reduce how far you count by taking the exponent modulo the loop length, just as you can find where the minute hand points after a huge number of minutes by reducing mod 60. Euler’s Theorem tells us that a safe modulus for the exponent is φ(n) (or even better, λ(n), the Carmichael function, which captures the exact joint loop length across all residues). The kicker: this clock analogy only works cleanly when a and n are coprime; otherwise, you might step off the clock into positions without inverses, breaking the nice cycle.

03Formal Definition

Let

n \geq 1

be an integer and define Euler’s totient function

φ (n)

as the number of integers in {1,2,…,n} that are coprime to n. If the prime factorization of n is n=

\prod

i^{α_{i}}

, then φ(n)=n

\prod_{p\mid n}\left

(1-

\frac{1}{p}\right

\prod_{i}

\left

(p_

i^{α_{i}}

-p_

i^{\alpha_i-1}\right

). Euler’s Theorem: For any integer a with gcd(a,n)=1, we have

a^{φ (n)}

≡1 (mod n). Equivalently,

a^{k + φ (n)}

≡

a^{k}

(mod n) for all

k \geq 0

. Group-theoretic view: The reduced residue system modulo n (the set of integers in [1,n] coprime to n) forms a multiplicative group modulo n, denoted (

Z

Z

\times

, of size

φ (n) .

By Lagrange’s Theorem in group theory, for any element a in this group,

a^{|G|}=a^{φ(n

)} is the identity element, i.e., 1 modulo n. Furthermore, the multiplicative order or

d_{n}

(a) (the smallest positive t with

a^{t}

≡1 mod n) satisfies or

d_{n}

(a) |

φ (n) .

A tighter universal exponent is given by the Carmichael function

λ (n),

the exponent of the group, with

a^{λ (n)}

≡1 (mod n) for all a coprime to n. Caveat: If gcd(a,n)≠1, then a is not in (

Z

Z

\times

, and Euler’s Theorem does not apply. Powers of a may enter zero divisors or reach 0 modulo prime powers dividing n, invalidating exponent-cycle reductions based on

φ (n) .

04When to Use

Fast modular exponentiation with huge exponents: If you need a^b mod n and can ensure gcd(a,n)=1, reduce b modulo φ(n) (or λ(n)) and then use binary exponentiation. This is common in competitive programming when b is enormous (even given as a decimal string).
Modular inverses under composite moduli: When gcd(a,n)=1, compute a^{φ(n)−1} mod n to get the inverse of a modulo n. This is essential when the modulus is not prime and Fermat’s Little Theorem cannot be used.
Cryptography (RSA): Key generation and decryption rely on properties like e·d≡1 (mod φ(n)); correctness of decryption follows from Euler’s Theorem (or Carmichael’s refinement).
Reducing exponent towers: For expressions like a^{b^{c}} mod n, you can reduce the top exponent modulo φ(n) recursively, provided the coprimality conditions hold at each step (or carefully switch to λ(n) and CRT).
Sanity checks and cycle detection: When analyzing periodicity of sequences x_{k+1}=a·x_k mod n with coprime a,n, the period divides φ(n) (or equals ord_n(a)). Avoid using it when gcd(a,n)≠1 without additional analysis; instead, factor n and use the Chinese Remainder Theorem to handle each prime power modulus separately.

⚠️Common Mistakes

Applying exponent reduction when gcd(a,n)≠1. Euler’s Theorem requires coprimality. If a shares a factor with n, reducing b modulo φ(n) can give a wrong answer. Remedy: factor n and use CRT per prime power, or avoid reduction.
Reducing b to b mod φ(n) unconditionally. If b<φ(n), the reduction changes nothing, but if b≥φ(n), many implementations reduce to b mod φ(n) and forget the “+φ(n)” safeguard to avoid mapping to exponent 0. A safer pattern for large b is a^{(b mod φ(n)) + φ(n)} when b is known to be large, ensuring at least one full cycle.
Forgetting that λ(n) often gives a smaller cycle than φ(n). Using φ(n) works but might be suboptimal; λ(n) is the true exponent of the group, reducing exponents further.
Computing φ(n) inefficiently. For a single n up to about 1e12, trial division by primes up to √n is fine; for many queries up to a bound, use a sieve. Mixing methods poorly can TLE.
Integer overflow in modular multiplication. When n fits in 64 bits but a·a can overflow 64-bit, use 128-bit temporaries (__int128 in C++) for safe multiplication.
Assuming negative or zero exponents are handled. Euler’s Theorem is about positive exponents in the multiplicative group. For inverses (negative exponents), ensure gcd(a,n)=1 and compute the inverse first.
Misusing Fermat’s Little Theorem with composite moduli. FLT requires prime moduli; Euler’s Theorem is the correct generalization for composite n with coprime bases.

Key Formulas

Euler Product for Totient

φ (n) = n p ∣ n \prod (1 - \frac{1}{p})

Explanation: Compute $φ (n)$ from the prime divisors of n. Multiply n by (1−1/p) for each distinct prime p dividing n.

Totient of a Prime Power

φ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p})

Explanation: For a prime power modulus, subtract the multiples of p from the total. This is the building block of $φ (n)$ for general n.

Euler’s Theorem

a^{φ (n)} \equiv 1 (mod n) if g cd (a, n) = 1

Explanation: Raising a coprime base a to $φ (n)$ returns the multiplicative identity modulo n. It guarantees a universal cycle length divisor for powers of a.

Fermat’s Little Theorem

a^{p - 1} \equiv 1 (mod p) if p is prime and g cd (a, p) = 1

Explanation: Special case of Euler’s Theorem when n is prime. A standard tool for prime moduli.

Order Divides Group Size

ord_{n} (a) ∣ φ (n)

Explanation: The multiplicative order of a modulo n divides the group size $φ (n)$ by Lagrange’s Theorem. This explains why exponents can be reduced modulo $φ (n) .$

Carmichael’s Theorem

a^{λ (n)} \equiv 1 (mod n) if g cd (a, n) = 1

Explanation: $λ (n)$ is the exponent of the multiplicative group modulo n, often smaller than $φ (n) .$ It can further reduce exponents compared to $φ (n) .$

Carmichael for Prime Powers

λ (p^{k}) = ⎩ ⎨ ⎧ φ (p^{k}) 12 2^{k - 2} p odd (p, k) = (2, 1) (p, k) = (2, 2) p = 2, k \geq 3

Explanation: Defines λ for prime powers. For odd primes, λ equals $φ;$ for 2-powers, the pattern differs and is smaller for $k \geq 3$ .

Exponent Reduction (Safe Form)

a^{b} \equiv a^{b mod φ (n)} (mod n) if g cd (a, n) = 1 and b \geq φ (n)

Explanation: When the exponent is large enough, you can reduce it modulo $φ (n) .$ Many implementations use $a^{(bm o d φ (n)) + φ (n)}$ to avoid mapping to exponent 0.

Divisor Sum Identity

d ∣ n \sum φ (d) = n

Explanation: The sum of φ over all divisors of n equals n. Useful in proofs and sanity checks.

CRT Two-Moduli Merge

x \equiv a (mod m), x \equiv b (mod n) \Rightarrow x \equiv a + (b - a) \cdot m^{- 1} mod n \cdot m (mod mn)

Explanation: One way to combine two congruences when m and n are coprime, using the inverse of m modulo n. This is handy when handling mod prime powers separately.

Binary Exponentiation Complexity

T_{pow} (b) = O (lo g b)

Explanation: Fast exponentiation requires logarithmic steps in the exponent by squaring. With reduction of the exponent via $φ (n),$ the effective cost often drops dramatically.

Complexity Analysis

The primary computational tasks around Euler’s Theorem are computing

φ (n)

and performing modular exponentiation. For a single modulus n, computing

φ (n)

via trial division over primes up to √n takes O(√n / log √n) trial divisions if you generate primes, or O(√n) simple divisions without sieving. This is fine for n up to about 10^12 in competitive settings with few test cases. For many moduli up to a bound N, a linear or modified sieve computes

φ (k)

for all

k \leq N

in O(N) or O(N log log N) time with O(N) memory. Binary (fast) exponentiation computes

a^{b}

mod n in O(log b) multiplications. If 64-bit multiplication can overflow during intermediate steps, use 128-bit temporaries (__int128) so each modular multiplication is O(1). When the exponent b is a huge decimal string of length L, computing b mod

φ (n)

takes O(L), and then powmod runs in O(log

φ (n)) .

Thus overall complexity becomes O(L + log

φ (n)) .

If gcd(a,n)≠1, Euler’s reduction does not apply; naive powmod is still O(log b), but handling very large b without reduction may be infeasible. A more advanced approach factors n and uses CRT per prime power, which introduces the cost of factoring (similar to φ computation) plus solving small-modulus exponentiations, often yielding practical speedups. Using the Carmichael function

λ (n)

can further reduce the exponent, but computing

λ (n)

requires the same factorization effort as

φ (n) .

Memory usage is modest: O(1) for single computations, O(N) for sieve-based precomputation of φ across a range of moduli.

Code Examples

Modular exponent with Euler reduction (fallback if not coprime)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 using u128 = unsigned __int128; // for safe 64-bit modular multiplication
5 using u64 = unsigned long long;
6 using i64 = long long;
7 
8 // Safe (a*b) % mod using 128-bit temporaries
9 static inline u64 mul_mod_u64(u64 a, u64 b, u64 mod) {
10     return (u128)a * b % mod;
11 }
12 
13 // Fast exponentiation: computes a^e mod mod
14 u64 powmod(u64 a, u64 e, u64 mod) {
15     if (mod == 1) return 0;
16     u64 res = 1 % mod;
17     a %= mod;
18     while (e > 0) {
19         if (e & 1) res = mul_mod_u64(res, a, mod);
20         a = mul_mod_u64(a, a, mod);
21         e >>= 1;
22     }
23     return res;
24 }
25 
26 // Compute phi(n) by trial division factorization
27 u64 phi_u64(u64 n) {
28     u64 result = n;
29     for (u64 p = 2; p * p <= n; ++p) {
30         if (n % p == 0) {
31             while (n % p == 0) n /= p;
32             result = result / p * (p - 1);
33         }
34     }
35     if (n > 1) {
36         // n is prime now
37         result = result / n * (n - 1);
38     }
39     return result;
40 }
41 
42 // Compute a^b mod n using Euler's Theorem if gcd(a,n)==1; otherwise no reduction.
43 u64 modexp_with_euler(u64 a, u64 b, u64 n) {
44     if (n == 1) return 0;
45     a %= n;
46     if (std::gcd((u64)a, (u64)n) == 1ULL) {
47         u64 ph = phi_u64(n);
48         // If b is large, reducing b modulo phi(n) is valid; if b >= phi(n), a^{b} ≡ a^{b % phi + phi}
49         // For 64-bit b we can just reduce and, if b >= ph, add ph to stay in the same residue class of exponents
50         u64 bmod = (ph == 0 ? 0 : b % ph);
51         if (b >= ph) bmod += ph; // safe form to avoid exponent 0 when cycles apply
52         return powmod(a, bmod, n);
53     } else {
54         // Fallback: can't reduce exponent; do plain fast pow
55         return powmod(a, b, n);
56     }
57 }
58 
59 int main() {
60     ios::sync_with_stdio(false);
61     cin.tie(nullptr);
62 
63     // Demo: compute a^b mod n for several cases
64     vector<tuple<u64,u64,u64>> tests = {
65         {2, 1000000000000ULL, 1000000007ULL}, // coprime, large b, prime modulus
66         {3, 123456789ULL, 1000ULL},           // not coprime (gcd(3,1000)=1 actually), still fine
67         {6, 1000000ULL, 1000ULL},             // not coprime (gcd(6,1000)=2), fallback
68         {10, 20ULL, 21ULL}                    // gcd(10,21)=1, use Euler reduction
69     };
70 
71     for (auto [a,b,n] : tests) {
72         u64 ans = modexp_with_euler(a,b,n);
73         cout << a << "^" << b << " mod " << n << " = " << ans << "\n";
74     }
75 }
76

This program computes a^b mod n efficiently. If a and n are coprime, it computes φ(n) by factorization and reduces the exponent using Euler’s Theorem with a safe rule: if b≥φ(n), use exponent (b mod φ(n)) + φ(n). If a and n are not coprime, it falls back to plain fast exponentiation without reduction. 128-bit temporaries ensure no overflow in modular multiplication.

Time: O(√n) to factor n once for φ(n), then O(log b) for exponentiation.Space: O(1) extra space.

Huge decimal exponent B (as string) with Euler reduction

1 #include <bits/stdc++.h>
2 using namespace std;
3 using u128 = unsigned __int128; using u64 = unsigned long long; using i64 = long long;
4 
5 static inline u64 mul_mod_u64(u64 a, u64 b, u64 mod){ return (u128)a*b % mod; }
6 
7 u64 powmod(u64 a, u64 e, u64 mod){
8     if (mod==1) return 0; u64 res = 1 % mod; a %= mod; while(e){ if(e&1) res = mul_mod_u64(res,a,mod); a = mul_mod_u64(a,a,mod); e>>=1; } return res;
9 }
10 
11 u64 phi_u64(u64 n){ u64 r=n; for(u64 p=2;p*p<=n;++p){ if(n%p==0){ while(n%p==0) n/=p; r = r/p*(p-1); } } if(n>1) r = r/n*(n-1); return r; }
12 
13 // Compare big decimal string B with small integer x; return true if B >= x
14 bool ge_str_uint64(const string &B, u64 x){
15     string xs = to_string(x);
16     if (B.size() != xs.size()) return B.size() > xs.size();
17     return B >= xs;
18 }
19 
20 // Compute B mod m where B is a nonnegative decimal string
21 u64 str_mod(const string &B, u64 m){
22     if (m==0) return 0; u64 r=0; for(char c: B){ r = ( (r*10ULL) + (c-'0') ) % m; } return r;
23 }
24 
25 // Compute a^B mod n, where B is a huge decimal string. Uses Euler reduction if gcd(a,n)=1.
26 u64 modexp_str_with_euler(u64 a, const string &B, u64 n){
27     if (n==1) return 0; a%=n;
28     if (std::gcd(a,n)==1ULL){
29         u64 ph = phi_u64(n);
30         u64 bmod = (ph==0?0:str_mod(B, ph));
31         // Safe exponent: if B >= ph, add ph to stay in correct cycle class
32         if (ge_str_uint64(B, ph)) bmod += ph;
33         return powmod(a, bmod, n);
34     } else {
35         // Not coprime; cannot reduce. If B is huge, this may be infeasible without CRT/case analysis.
36         // As a fallback, if B fits in 64-bit, compute directly; otherwise, handle small special cases.
37         // Here we attempt to parse if small; otherwise we cap (demonstrative only).
38         if (B.size() <= 19){
39             unsigned long long b = 0; for(char c: B){ b = b*10 + (c-'0'); }
40             return powmod(a, b, n);
41         } else {
42             // In practice, factor n, split by CRT, and handle each prime power.
43             // We return 0 here only as a placeholder to indicate the need for advanced handling.
44             // Do NOT do this in production; implement CRT for robustness.
45             return 0; 
46         }
47     }
48 }
49 
50 int main(){
51     ios::sync_with_stdio(false); cin.tie(nullptr);
52     // Examples
53     // 1) Coprime case with huge exponent string
54     u64 a = 7, n = 1000000007ULL; string B = string(100000, '9'); // 10^5-digit exponent of all 9s
55     cout << "7^(10^5 9s) mod 1e9+7 = " << modexp_str_with_euler(a,B,n) << "\n";
56 
57     // 2) Composite modulus, still coprime base
58     a = 10; n = 21; B = "12345678901234567890";
59     cout << "10^B mod 21 = " << modexp_str_with_euler(a,B,n) << "\n";
60 
61     // 3) Not coprime base-modulus (fallback path)
62     a = 6; n = 1000; B = "2000000000000"; // large exponent; here we cannot reduce safely
63     cout << "6^B mod 1000 (naive/fallback) = " << modexp_str_with_euler(a,B,n) << "\n";
64 }
65

This program handles exponents B that are too large to fit in 64 bits by reading B as a decimal string. When gcd(a,n)=1 it computes φ(n), reduces B modulo φ(n) in O(|B|), and applies the safe +φ(n) trick when B≥φ(n). If gcd(a,n)≠1, naive reduction is unsafe; a robust solution would factor n and use CRT per prime power. The example includes a placeholder return for that difficult branch to highlight the need for deeper techniques.

Time: Coprime case: O(√n) to factor n, O(|B|) to reduce B modulo φ(n), and O(log φ(n)) for powmod.Space: O(1) additional space (beyond storing the string).

Modular inverse via Euler’s Theorem (composite modulus)

1 #include <bits/stdc++.h>
2 using namespace std;
3 using u128 = unsigned __int128; using u64 = unsigned long long;
4 
5 static inline u64 mul_mod_u64(u64 a, u64 b, u64 mod){ return (u128)a*b % mod; }
6 
7 u64 powmod(u64 a, u64 e, u64 mod){ if(mod==1) return 0; u64 r=1%mod; a%=mod; while(e){ if(e&1) r=mul_mod_u64(r,a,mod); a=mul_mod_u64(a,a,mod); e>>=1; } return r; }
8 
9 u64 phi_u64(u64 n){ u64 r=n; for(u64 p=2;p*p<=n;++p){ if(n%p==0){ while(n%p==0) n/=p; r = r/p*(p-1); } } if(n>1) r = r/n*(n-1); return r; }
10 
11 // Returns {has_inverse, inverse}
12 pair<bool,u64> inverse_euler(u64 a, u64 n){
13     a %= n; if (n==1) return {false,0};
14     if (std::gcd(a,n) != 1ULL) return {false,0};
15     u64 ph = phi_u64(n);
16     u64 inv = powmod(a, ph - 1, n); // a^{phi(n)-1} ≡ a^{-1} mod n
17     return {true, inv};
18 }
19 
20 int main(){
21     ios::sync_with_stdio(false); cin.tie(nullptr);
22 
23     vector<pair<u64,u64>> qs = { {3,10}, {7,40}, {12,35}, {2,8} };
24     for (auto [a,n] : qs){
25         auto [ok, inv] = inverse_euler(a,n);
26         cout << "Inverse of " << a << " mod " << n << ": ";
27         if (!ok) cout << "does not exist";
28         else cout << inv << " (check: " << ( ( (__int128)a*inv ) % n ) << ")";
29         cout << "\n";
30     }
31 }
32

Using Euler’s Theorem, when gcd(a,n)=1 the modular inverse is a^{φ(n)−1} mod n. This code computes φ(n) via factorization and then runs powmod. It reports the absence of an inverse if a and n are not coprime.

Time: O(√n) to factor n for φ(n), then O(log φ(n)) for exponentiation.Space: O(1) extra space.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	using u128 = unsigned __int128; // for safe 64-bit modular multiplication
5	using u64 = unsigned long long;
6	using i64 = long long;
7
8	// Safe (a*b) % mod using 128-bit temporaries
9	static inline u64 mul_mod_u64(u64 a, u64 b, u64 mod) {
10	return (u128)a * b % mod;
11	}
12
13	// Fast exponentiation: computes a^e mod mod
14	u64 powmod(u64 a, u64 e, u64 mod) {
15	if (mod == 1) return 0;
16	u64 res = 1 % mod;
17	a %= mod;
18	while (e > 0) {
19	if (e & 1) res = mul_mod_u64(res, a, mod);
20	a = mul_mod_u64(a, a, mod);
21	e >>= 1;
22	}
23	return res;
24	}
25
26	// Compute phi(n) by trial division factorization
27	u64 phi_u64(u64 n) {
28	u64 result = n;
29	for (u64 p = 2; p * p <= n; ++p) {
30	if (n % p == 0) {
31	while (n % p == 0) n /= p;
32	result = result / p * (p - 1);
33	}
34	}
35	if (n > 1) {
36	// n is prime now
37	result = result / n * (n - 1);
38	}
39	return result;
40	}
41
42	// Compute a^b mod n using Euler's Theorem if gcd(a,n)==1; otherwise no reduction.
43	u64 modexp_with_euler(u64 a, u64 b, u64 n) {
44	if (n == 1) return 0;
45	a %= n;
46	if (std::gcd((u64)a, (u64)n) == 1ULL) {
47	u64 ph = phi_u64(n);
48	// If b is large, reducing b modulo phi(n) is valid; if b >= phi(n), a^{b} ≡ a^{b % phi + phi}
49	// For 64-bit b we can just reduce and, if b >= ph, add ph to stay in the same residue class of exponents
50	u64 bmod = (ph == 0 ? 0 : b % ph);
51	if (b >= ph) bmod += ph; // safe form to avoid exponent 0 when cycles apply
52	return powmod(a, bmod, n);
53	} else {
54	// Fallback: can't reduce exponent; do plain fast pow
55	return powmod(a, b, n);
56	}
57	}
58
59	int main() {
60	ios::sync_with_stdio(false);
61	cin.tie(nullptr);
62
63	// Demo: compute a^b mod n for several cases
64	vector<tuple<u64,u64,u64>> tests = {
65	{2, 1000000000000ULL, 1000000007ULL}, // coprime, large b, prime modulus
66	{3, 123456789ULL, 1000ULL}, // not coprime (gcd(3,1000)=1 actually), still fine
67	{6, 1000000ULL, 1000ULL}, // not coprime (gcd(6,1000)=2), fallback
68	{10, 20ULL, 21ULL} // gcd(10,21)=1, use Euler reduction
69	};
70
71	for (auto [a,b,n] : tests) {
72	u64 ans = modexp_with_euler(a,b,n);
73	cout << a << "^" << b << " mod " << n << " = " << ans << "\n";
74	}
75	}
76

1	#include <bits/stdc++.h>
2	using namespace std;
3	using u128 = unsigned __int128; using u64 = unsigned long long; using i64 = long long;
4
5	static inline u64 mul_mod_u64(u64 a, u64 b, u64 mod){ return (u128)a*b % mod; }
6
7	u64 powmod(u64 a, u64 e, u64 mod){
8	if (mod==1) return 0; u64 res = 1 % mod; a %= mod; while(e){ if(e&1) res = mul_mod_u64(res,a,mod); a = mul_mod_u64(a,a,mod); e>>=1; } return res;
9	}
10
11	u64 phi_u64(u64 n){ u64 r=n; for(u64 p=2;pp<=n;++p){ if(n%p==0){ while(n%p==0) n/=p; r = r/p(p-1); } } if(n>1) r = r/n*(n-1); return r; }
12
13	// Compare big decimal string B with small integer x; return true if B >= x
14	bool ge_str_uint64(const string &B, u64 x){
15	string xs = to_string(x);
16	if (B.size() != xs.size()) return B.size() > xs.size();
17	return B >= xs;
18	}
19
20	// Compute B mod m where B is a nonnegative decimal string
21	u64 str_mod(const string &B, u64 m){
22	if (m==0) return 0; u64 r=0; for(char c: B){ r = ( (r*10ULL) + (c-'0') ) % m; } return r;
23	}
24
25	// Compute a^B mod n, where B is a huge decimal string. Uses Euler reduction if gcd(a,n)=1.
26	u64 modexp_str_with_euler(u64 a, const string &B, u64 n){
27	if (n==1) return 0; a%=n;
28	if (std::gcd(a,n)==1ULL){
29	u64 ph = phi_u64(n);
30	u64 bmod = (ph==0?0:str_mod(B, ph));
31	// Safe exponent: if B >= ph, add ph to stay in correct cycle class
32	if (ge_str_uint64(B, ph)) bmod += ph;
33	return powmod(a, bmod, n);
34	} else {
35	// Not coprime; cannot reduce. If B is huge, this may be infeasible without CRT/case analysis.
36	// As a fallback, if B fits in 64-bit, compute directly; otherwise, handle small special cases.
37	// Here we attempt to parse if small; otherwise we cap (demonstrative only).
38	if (B.size() <= 19){
39	unsigned long long b = 0; for(char c: B){ b = b*10 + (c-'0'); }
40	return powmod(a, b, n);
41	} else {
42	// In practice, factor n, split by CRT, and handle each prime power.
43	// We return 0 here only as a placeholder to indicate the need for advanced handling.
44	// Do NOT do this in production; implement CRT for robustness.
45	return 0;
46	}
47	}
48	}
49
50	int main(){
51	ios::sync_with_stdio(false); cin.tie(nullptr);
52	// Examples
53	// 1) Coprime case with huge exponent string
54	u64 a = 7, n = 1000000007ULL; string B = string(100000, '9'); // 10^5-digit exponent of all 9s
55	cout << "7^(10^5 9s) mod 1e9+7 = " << modexp_str_with_euler(a,B,n) << "\n";
56
57	// 2) Composite modulus, still coprime base
58	a = 10; n = 21; B = "12345678901234567890";
59	cout << "10^B mod 21 = " << modexp_str_with_euler(a,B,n) << "\n";
60
61	// 3) Not coprime base-modulus (fallback path)
62	a = 6; n = 1000; B = "2000000000000"; // large exponent; here we cannot reduce safely
63	cout << "6^B mod 1000 (naive/fallback) = " << modexp_str_with_euler(a,B,n) << "\n";
64	}
65