GCD with two big large numbers

Question

How to find the $\gcd(2020^{1830} +2, 2020^{1830} -2)$? I can't seem to find the gcd because of the large numbers.

Answer 1

By the Euclidean algorithm,

$$(2020^{1830}+2,2020^{1830}-2)\to(2020^{1830}-2,4)^*\to(4,2)\to(\color{green}2,0)$$

---

$^*$It is obvious that $2020^{1830}=2^{1830}1010^{1830}$ is a multiple of $4$.

Answer 2

Let $2020^{1830}=a$. So you want $\gcd(a+2,a-2)$. Lets say this value be $d$. Thus, $d|a+2,d|a-2\implies d|4\implies d\in\{1,2,4\}$. But $4\not| a+2$ as $4|a$. Thus, $d\neq 4$ but $a+2,a-2$ are even, so $d=2$.

Answer 3

$\gcd(a,b) = \gcd(b,a \bmod b)$ is key.

So your gcd equals $\gcd(2010^{1830}-2, 4)$ so ask yourself, what is the remainder of $2010^{1830}-2$ modulo $4$? It's clear that it's $2$ as the power is divisible by $4$. So we get $\gcd(4,2)=2$ in the end.

Answer 4

$gcd(a,b)=gcd(a,b+am)$ so

$gcd(2020^{1830}-2,2020^{1830}+2)$

$=gcd(2020^{1830}-2,2×2+(2020^{1830}-2))$

$=gcd(2020^{1830}-2,4)$

---

now consider $(2×1010)^{1830}-2=2^{1830}×1010^{1830}-2=2(2^{1829}×1010^{1830}-1)$ then obviously $gcd(2020^{1830}-2,4)=2$

so $gcd(2020^{1830}-2,2020^{1830}+2)=2$

Answer 5

$$g = \gcd(2020^{1830} +2, 2020^{1830} -2)$$

Let $N = 2020^{1830}$. So you want $\gcd(N +2, N -2)$

If $g | N+2$ and $g | N-2$, then $g | (N+2)-(N-2)$, that is to say $g | 4$.

So $g$ must be $1, 2$ or $4$.

Since $2020$ is a multiple of $4$, then $4 | N$. Hence $ 4 \not | N+2$.

Hence $g=2$