# Greatest Common Divisor With large numbers

Find $\gcd(300^{40},2^{57})$ I know how to use Euclidean Algorithm for smaller numbers, but with these large numbers I'm not sure how to do it.

• Note that $300^{40}$ is divisible by $2^{80}$. – carmichael561 Mar 1 '16 at 2:49
• This might help: $300^{40}=(2^8+2^5+2^3+2^2)^{40}$ – Yeah.. Mar 1 '16 at 2:53

Prime Factorize Each: $$300^{40}=2^{80}3^{40}5^{80}$$ $$2^{57}=2^{57}$$.
Thus, notice that $2^{57}|300^{40}$, and so the $\gcd$ is $2^{57}$.
In general, when approaching the $\gcd(a^{b}, c^{d})$, the easiest method would be to factorize $a$ and $c$.