GCD and exponentiation of large numbers

Question

I am solving a problem involving $\gcd$ of two very large numbers. Given three numbers $a,b,n$, I have to find $\gcd(a,b^n)$. So for example $$a,b,n=119929244861828206, 521483382396998375, 4838134431180356$$ I used fast modular exponentiation to find $$521483382396998375^{4838134431180356}\bmod 1000000007=473264774$$ Then I used python's math.gcd module to calculate $\gcd(119929244861828206,473264774)$ and got the answer as 2 but the answer is given as 83. I am not sure what mistake I did, so please guide me.

Answer 1

If you use the Euclidean algorithm, the first step can be chosen to be computing $b^n$ mod $a$, then compute $a$ mod that, etc. until you get 0. Then back up a step to get the actual GCD, then finally mod by 1000000007 at the end.

Modding by the final modulus at the start changes the result compared to doing it at the end. For instance consider that gcd(11,4) mod 3 is 1 but gcd(11 mod 3,4) is 2.