How to calculate the gcd of (3^{100!}-1,116)?

Question

I have to find out the result of $$(3^{100!}-1,116)$$

This is an exercise after the chapter of integer factorization and now I need help.

Answer 1

$116 =4\cdot 29 $.

$3^{100!}-1 =9^{100!/2}-1 =(9-1)\sum_{k=0}^{100!/2-1} 9^k =8\sum_{k=0}^{100!/2-1} 9^k $ so the gcd is either $4$ or $4\cdot 29$.

Since $a^{29} \equiv a \bmod 29$, $\bmod 29$ we have $3^{100!} \equiv 3^{100! \bmod 28} \equiv 3^0 \equiv 1 $ since $28 | 100!$.

Therefore $3^{100!} \equiv 1 \bmod 29 $ so the gcd is 116.