Euler Phi Function

\(\phi(n)\) denote the number of integers of b such that \(1<=b<=n\) such that gcd(b,n) = 1. \(\phi(n) = n-1\), if and only if n is prime. If the integer \(n > 1\) has the prime factorization \(n=p1^{k1} p2^{k2} .... pr^{kr}\), then \(\phi(n) = n * \Pi (1 - 1 / PF)\).

Code

ll EulerPhi(ll N)
{
    ll PF_idx = 0, PF = primes[PF_idx], ans = N;
    while( PF *PF <= N)
    {
        if(N % PF == 0)
            ans -= ans / PF;
        while(N % PF == 0)
            N /= PF;
        PF = primes[++PF_idx];
    }
    if (N != 1) ans -= ans / N;
    return ans;
}

Euler’s Theorem

Let n be a positive integer, and let a be an integer that is relatively prime to n. Then, \(a^{\phi(n)} \, \cong \, 1 \, (mod \, n)\), where \(\phi(n)\) is Euler’s phi function.

Fermat’s Little Theorem

Let n be a positive prime integer, and let a be an integer that is relatively prime to n. Then, \(a^{(n-1)} \, \cong \, 1 \, (mod \, n)\).

Exponentiation

Given two numbers be b and n and the exponentiation is \(b^n\). To find \(b^n\), we can simply multiply \(b * .... * b\), n times. The brute force way of solving it will be in \(\mathcal{O}(n)\), but we can do better. One way is by divide and conquer method and it as time complexity \(\mathcal{O}(\log(n))\) and takes little stack space. The other approach is by using binary exponentiation; \(b^n\) expressed as \(b^{n_{base_{2}}}\). i.e \(5^3 = 5^{11_{2}} = 5^{2} * 5^{1}\).

Code - Binary Exponentiation

long long pow(long long b, long long n, long long p)
{
    long long res = 1, ans = b;
    for(; n >0 ; n = n >> 1)
    {
        if(n & 1)
            res = ( res * ans ) % p;
        ans = (ans * ans) % p;
    }
    return res;
}

Modular Multiplicative Inverse

Consider equation \(b*b^{-1}=1 \, mod \, n\), given b and n find \(b^{-1}\). The modular inverse can be found using the linear diophantine equation with the help of extended Euclidean algorithm. Note, modular inverse exists if and only if b and m are relatively prime (i.e. gcd(b, m) = 1). The inverse can also be found using Binary Exponentiation with the help of Euler’s theorem. Consider the equation from euler theorem where \(a^{\phi(m)} = 1 \, mod \, m\), and gcd(b, m) = 1 then modular inverse is \(a^{\phi(m)-1} = a^{-1} \, mod \, m\). We can find \(a^{\phi{(m)}-1}\) using binary exponentiation.

• ← Previous Post
• Next Post →