Add Me!Close Menu Navigation

Infinite GCD

Compute gcd(2002 + 2, 20022+2, 20023+2, …)

In order to evaluate \gcd(2002 + 2, 2002^2+2, 2002^3+2, \ldots), we first evaluate (2004, 2002^2+2). Before we start the Euclidean algorithm, we can simplify this problem considerably by rewriting 2002^2+2 in terms of 2004n + k\ :\ n,k \in \mathbb N

(1)   \begin{align*} 2002^2 + 2 &= 2004n + k \\ &= (2002 + 2)n + k \\ &= 2002n + (2n+k) \\ &= 2002\underbrace{(2012)}_n + \underbrace{(4004+k)}_{4004+k=2} \\ &= 2004(2012) - 4002 \\ &= 2004(2010) + 4008 - 4002 \\ &= 2004(2010) + 6 \end{align*}

Substituting 2002^2+2 from (1), we now need to find (2004, 2004(2010) + 6)

(2)   \begin{align*} (2004, 2004(2010) + 6) &= (2004, 2004\overbrace{(2009)}^{\mathclap{decreasing}} + 6) \\ &= (2004, 2004(2008) + 6) \\ &= \left. \vdots \right\rbrace {2010 \mbox{ times}}\\ &= (2004, 2004 + 6) \\ &= (2004, 6) \\ &= 6 \end{align*}

From (2), we know that \gcd(2002 + 2, 2002^2+2, 2002^3+2, \ldots) is at most 6. Since 2|(2002^n+2)\fa n \in \mathbb N, all we need to do is prove or disprove 3|(2002^n+2)

This is an easy proof to make.

(3)   \begin{align*} (2002^n + 2) \mod 3 = 0 &\iff (2002^n \mod 3) + (2 \mod 3) = 3 \\ &\iff 2002^n \mod 3 = 1 \end{align*}

Therefore, all we need to show is that 2002^n \mod 3 = 1. Notice that 3|2001 so

    \begin{align*} 2002 \mod 3 = 1 &\implies 2002^n \mod 3 \\ &= (2002 \mod 3)^n \mod 3\\ &= 1\blacksquare \end{align*}

Therefore, because 2|(2012^n+2) \wedge 3|(2012^n+2), then it must be the case that \gcd(2002 + 2, 2002^2+2, 2002^3+2, \ldots) = 6. \blacksquare

Posted By Lee

Woosh