Story of Totient Function

To solve this problem we need to know about prime gaps. In 1018 range, the maximum difference two consecutive prime is 1442.

If A is a prime, then ϕ(A) = A - 1. Let P be the next prime after A. For any integer X from (A + 1) to (P - 1), ϕ(X) ≤ ϕ(A). So P will be our answer. We can use Miller-Rabin to test prime. And from the prime gap, we can say that we will get a prime after a thousand checking.

When A is not prime, ϕ(A) will drop down depending on the factors it has. So, we can quickly find a suitable B that exceeds ϕ(A). To compute the ϕ values for large numbers, we can use pollard-rho for prime factorization and then find the ϕ value.