　$ \textrm{gcd} (8n + 9, n^{9} + 1) = g$ とする．いま，
$$(8n)^9 + 9^9 = (8n + 9)((8n)^{8} - 9 \cdot (8n)^{7} + 9^2 \cdot (8n)^{6} - \dots + 9^{8})$$
および
$$(8n)^{9} + 8^{9} = 8^{9} (n^{9} + 1)$$
も $g$ で割り切れるので，$9^{9} - 8^{9}$ も $g$ で割り切れ，特に $g \leq 9^{9} - 8^{9}$ が従う．また，$9^{9} - 8^{9}$ と $8$ は互いに素なので，$8n_1 + 9$ が $9^{9} - 8^{9}$ の倍数となるような正整数 $n_1$ が存在する．この $n_1$ について，
$$ (8n_{1})^{9} + 9^{9} + (8^{9} - 9^{9})= 8^{9} ({n_{1}}^{9} + 1)$$ 
も $9^{9} - 8^{9}$ の倍数となるが，$8^{9}$ と $9^{9} - 8^{9}$ が互いに素であることから，${n_{1}}^{9} + 1$ が $9^{9} - 8^{9}$ の倍数であることが従う．よって，$\textrm{gcd} (8n_{1} + 9, {n_{1}}^{9} + 1) = 9^{9} - 8^{9}$ が分かるため，求める最大値は
$$ 9^9 - 8^9 = \mathbf{253202761} $$
となる．
公式解説
https://onlinemathcontest.com/contests/omc236/editorial/10575
　正の奇数 $x$ と $0$ でない整数 $y$ について $\mathrm{gcd}(x,y)=\mathrm{gcd}(x,8y)$ が成立する．以下 $x=8n+9$ としてこれを断りなく用いる．

　$\mathrm{gcd}(8n+9,n^9+1)$ に互除法を適用することを考えると，以下のような変形ができる：

$$\mathrm{gcd}(8n+9,n^9+1) = \mathrm{gcd}(8n+9,8n^9+8) = \mathrm{gcd}(8n+9,-9n^8+8)=\mathrm{gcd}(8n+9,9n^8-8)$$
$$\mathrm{gcd}(8n+9,9n^8-8) = \mathrm{gcd}(8n+9,72n^8-64) = \mathrm{gcd}(8n+9,-81n^7-64)=\mathrm{gcd}(8n+9,81n^7+64)$$

　より一般に，$t$ を $0$ 以上 $8$ 以下の整数として次のような変形が行える：
$$\mathrm{gcd}(8n+9,9^tn^{9-t}+(-8)^t) = \mathrm{gcd}(8n+9,8 \cdot 9^tn^{9-t}-(-8)^{t+1})$$
$$=\mathrm{gcd}(8n+9,-9^{t+1}n^{9-(t+1)}-(-8)^{t+1})=\mathrm{gcd}(8n+9,9^{t+1}n^{9-(t+1)}+(-8)^{t+1})$$

　よって，$\mathrm{gcd}(8n+9,n^9+1) = \mathrm{gcd}(8n+9,9^9-8^9) \leq 9^9-8^9$ が成立し，$(9^9-8^9)-9$ が $8$ の倍数であることは容易に確認できるため，先の等号を成立させるような正整数 $n$ が確かに存在する．よって求める最大値は，

$$9^9-8^9 = \mathbf{253202761}$$

となる．
互除法だけで解く
https://onlinemathcontest.com/contests/omc236/editorial/10575/735
　$n$ を正整数とするとき，$8n + 9$ と $n^{9} + 1$ の最大公約数としてあり得る最大値が存在するので，これを求めてください．