I need to compute $gcd(2^{180!},15770708441)$.
I tried to use the Euclidean Algorithm via the implemented Python function, but it takes far too long. My teacher mentioned that we should not compute $2^{180!}$ but rather $2^{180!} \bmod 15770708441$ to keep the numbers small. But if I am not misaking this is exactly what the Euclidean algorithm does.
Am I doing something wrong?
Best Answer
No computations or algorithm needed: The second number is odd, so has no (prime) factor $2$ at all.
The first number only has prime factor $2$ (repeated $180!$ times). So they have no common divisor except $1$.