　$n^{13\times 8}-1$ は $n^8-1$ の倍数なので，
$$a_n = \gcd(n^8-1,n^{13}-2) \leq \gcd(n^{13\times8}-1,n^{13}-2)$$
が成立する．ここで， 
$$n^{13\times8}-1 = (n^{13}-2)(n^{13\times7}+2^1n^{13\times6}+2^2n^{13\times5}+\cdots+2^7)+(2^8-1)$$
と変形できるので，$a_n \leq 2^8-1 = 255$ である．\
　以下 $a_n = 255$ となる $n$ を考える．
$n^8-1 \equiv 0 \pmod{255}$ かつ $n^{13}-2 \equiv 0 \pmod{255}$ であることは，$n \equiv 32 \pmod{255}$ であることと同値である．これは $255 = 3\times5\times17$ より中国剰余定理を用いれば素早く導ける． よって，$n \equiv 32 \pmod{255}$ であるときかつそのときに限り，$a_n = 255$ となることが分かる．\
　$255m+32 \leq 10000$ なる整数 $m$ の最大値は $39$ なので，
求める値は $$\sum_{m = 0}^{39}(255m+32) = \textbf{200180}$$ となる．
公式解説
https://onlinemathcontest.com/contests/omc123/editorial/3131
　ユークリッドの互除法で次数を下げていく方法です．
***
　一般に，自然数 $a,b,p$ に対して
$$\gcd(a,b) = \gcd(b,a - pb) \tag{1}$$ 
が従う．$(1)$ を繰り返し用いて
$$\gcd(n^{13} - 2,n^8 -1) = \gcd(n^8 -1,n^5 - 2)=\gcd(n^5 - 2,2n^3 - 1)$$
　ここで，$2n^3 - 1$ は奇数なので
$$\gcd(n^5 - 2,2n^3 - 1) = \gcd(2n^5 - 4,2n^3 - 1)$$
が成立する．再度 $(1)$ を繰り返し用いて
$$\gcd(2n^5 - 4,2n^3 - 1) = \gcd(2n^3 - 1,n^2 - 4) = \gcd(n^2 - 4,8n - 1)$$
　ここで，$8n - 1$ は奇数なので
$$\gcd(n^2 - 4,8n - 1) = \gcd(8n^2 - 32,8n - 1)$$
が成立する．再度 $(1)$ を繰り返し用いて
$$\gcd(8n^2 - 32,8n - 1)  = \gcd(8n - 1,n - 32) = \gcd(n - 32,255)$$
　以上より $a_n = \gcd(n - 32,255)$ と表せるので，$n \equiv 32 \pmod {255}$ のときに $a_n$ は最大値 $255$ をとる．\
　あとは公式解説と同様に計算することで，求める値は $\mathbf{200180}$ となる．
ユークリッドの互除法を用いた解法
https://onlinemathcontest.com/contests/omc123/editorial/3131/138
　正の整数 $a,b$ に対して，その最大公約数を $\gcd(a,b)$ と表します．\
　$2$ 以上の整数 $n$ に対して，正の整数 $a_n$ を
$$a_n = \gcd(n^8-1,n^{13}-2)$$
で定めます．$n$ を動かしたとき $a_n$ には最大値が存在するので，その値を $M$ とおきます．$a_n = M$ をみたす $2$ 以上 $10000$ 以下の整数 $n$ の総和を求めてください．