Note that for each by Euler’s theorem. Hence
using a result from this post. Now if , then the GCD on the right-hand side is equal to . Otherwise divides the GCD, so that
By the Chinese Remainder Theorem we can choose to be a primitive root modulo for simultaneously. Hence equality can be achieved in for any . Further, if one of the is and one is congruent to then the GCD in is exactly , so that equality is achieved in . So is the best uniform bound if , while if then is uniformly the best possible.