Fermat's Little Theorem and Euler's Theorem

Fermat and Euler describe periodicity of powers of invertible residues. Fermat applies to a prime modulus p and a nonzero residue; Euler applies to any positive modulus m when the base is coprime to m. These conditions determine when exponent reduction is valid. The program accepts an exponent as decimal text, demonstrating how a theorem can avoid storing a huge integer exponent.

Prerequisites: Totient; modular inverse; Binary Exponentiation.

Build the idea

1. 1. State the two theorems precisely

   For prime p and gcd(a,p)=1, a^(p−1)≡1 (mod p). Euler generalizes this to a^φ(m)≡1 (mod m) when gcd(a,m)=1. Fermat is the case φ(p)=p−1. The statements concern invertible residues, not arbitrary bases. For m=1 all residues are zero; this lesson restricts m≥2.

   $$a^{\phi \left(m\right)}\equiv 1\left(\mathrm{mod}m\right)$$

2. 2. Explain the permutation proof

   Multiplication by a permutes the φ(m) invertible residue classes: if ar≡as, the inverse/coprimality of a forces r≡s. Multiply all classes before and after this permutation. Their products differ by a^φ(m), and the class product itself is invertible, so it can be cancelled. That yields Euler’s theorem. This proof also explains exactly where coprimality is essential.

3. 3. Reduce a huge decimal exponent

   Write E=q·φ(m)+r. Then a^E≡a^r for coprime a. Scan decimal digits with remainder=(10·remainder+digit)%φ(m); the remainder after each prefix equals that prefix’s numeric value modulo φ(m). No large-integer parser is needed. Binary exponentiation evaluates the reduced power.

4. 4. Work composite and prime examples

   For m=10, φ=4 and gcd(3,10)=1. Exponent 12345 has remainder 1 modulo 4, so 3^12345≡3. For prime 7, 3^8 reduces exponent modulo 6 to 2, yielding 2. But with a=2,m=8, φ=4 and exponent 4, naive reduction gives exponent zero and result 1, while 2^4 mod 8=0. The program rejects the noncoprime reduction rather than printing that false result.

5. 5. Connect inverses and actual periods

   Euler implies a^(φ(m)−1) is an inverse when coprime; Extended Euclid avoids factoring m to obtain one. The true multiplicative order can be smaller than φ(m), but using φ is always valid under the theorem. Computing φ may itself be expensive for large m, so exponent reduction is not automatically faster than ordinary binary exponentiation when E already fits a machine integer.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Connect inverses and actual periods Euler implies a^(φ(m)−1) is an inverse when
// coprime; Extended Euclid avoids factoring m to obtain one.
#include<iostream>
#include<string>
#include<numeric>
using ll=long long;
ll power(ll a,unsigned long long exponent,ll mod){
    a=(a%mod+mod)%mod;
    ll result=1%mod;
    while(exponent>0){
        if(exponent&1ULL){
            result=result*a%mod;
        }
        a=a*a%mod;
        exponent>>=1;
    }
    return result;
}
ll phi(ll n){
    ll answer=n;
    for(ll p=2;p<=n/p;++p){
        if(n%p==0){
            answer-=answer/p;
            do{
                n/=p;
            }
            while(n%p==0);
        }
    }
    if(n>1){
        answer-=answer/n;
    }
    return answer;
}
int main(){
    ll a,m;
    std::string exponent;
    std::cin>>a>>m>>exponent;
    a=(a%m+m)%m;
    if(std::gcd(a,m)!=1){
        std::cout<<"COPRIMALITY REQUIRED\n";
        return 0;
    }
    ll period=phi(m),reduced=0;
    for(char digit:exponent){
        reduced=(reduced*10+(digit-'0'))%period;
    }
    std::cout<<period<<' '<<reduced<<'\n'<<power(a,(unsigned long long)reduced,m)<<'\n';
}

Complexity analysis

O(√m+L+log m) time: trial factorization of m, scanning L exponent digits, then binary exponentiation. O(L) storage holds the exponent string; arithmetic state is constant-sized. Here 2≤m≤10^9 and L≤100000. A streaming digit interface could avoid storing the full exponent, but this example reads a token.

Example input and output

Read a m E with |a|≤10^18, 2≤m≤10^9 and a nonempty decimal exponent E of length≤100000 (leading zeros allowed). If coprime, print φ(m), E mod φ(m), then a^E mod m. Otherwise print COPRIMALITY REQUIRED.

Input

3 10 12345

Output

4 1
3

The four invertible classes modulo 10 give period 4; 12345 mod 4=1, leaving 3¹ mod 10.

Practical applications

Use for huge-exponent modular problems with an invertible base, period arguments and inverse derivations. Binary exponentiation is sufficient for ordinary machine-sized exponents. Noncoprime huge powers need additional factor/valuation reasoning rather than unqualified Euler reduction.

Check your understanding

Why does a=2,m=8 prevent direct Euler exponent reduction?

Put it into practice

Test E="0", m=2, and a noncoprime counterexample.