By Euler's Theorem, if gcd(a, n) = 1, . If m happens to be a prime, then phi(m) = m - 1.

Even when gcd(a, n) > 1, the following holds: If b ≥ φ(m), . When m is large and you cannot efficiently factor it to compute φ(m) and b is given in decimal form, you can still use fast exponentiation. Process digits of b one by one starting from the most significant one and use a^10b + c = (a^b)¹⁰ × a^c.