How to calculate the $\gcd(10^6 +1 , 10^2 +1)$? I can't really figure out how to approach this question..
I have tried to factor 10^2 +1 out of 10^6 +1 , however, the '+1' part makes it difficult. 
$10^6 + 1 = (10^2 +1) \cdot 10^3 + 899000$,
$10^2 + 1 = 899000 \cdot ...? $
Here is where I get stuck, because $899000$ is way bigger than $10^2 + 1$..
Does anyone know how to approach this?
Thanks!

Well, the "throw rocks at it until it falls off a cliff approach":
$\gcd (10^6 + 1, 10^2 + 1) = \gcd([10^6 + 1] - 10^4(10^2 + 1), 10^2 + 1)$
$=\gcd (-10^4 + 1, 10^2 + 1) = \gcd(-10^4 + 1 + 10^2(10^2 + 1), 10^2 + 1)$
$= \gcd(10^2 + 1,10^2+1) = 10^2 + 1$.
....
There's also the insightful.  $x^n - 1 = (x-1)(x^{n-1} + x^{n-2} + .... + x + 1)$ and if $n$ is odd then $x^n + 1 = (x+1)(x^{n-1} - x^{n-2} + .... + x^2 - x + 1)$ and let $x = 10^2$ and $n = 3$ and... oh,... that's Mike Rozenberg's elegant answer... isn't it?
