пусть НОД(f(n),g(n))>1 — и, соответственно, делится на какое-то простое p
это значит, что по модулю p у многочленов f и g есть общий корень (а именно, n), то есть Res(f,g) = 0 mod p
в данном случае результант равен¹ простому числу p=1968751, поэтому если НОД не 1, то он равен этому числу (и это уже намекает, что пример вряд ли найдется среди небольших n… а, скажем, для n^17+9 и (n+1)^17+9 получается простое число порядка 10^50)
остается найти² корни пятой степени из -5 по этому модулю (96502, 533360, 533361, 1066696, 1707583) и поискать среди них³ отличающиеся на 1
окончательно получаем, что НОД равен 1968751 для n=533360+1968751m (и 1 иначе)
(можно обойтись и без слова 'результант': шагами a la алгоритм Евклида (f,g)→(af+bg,f) нетрудно получить, что в идеале (f,g) лежит число (паразитический множитель)×1968751 — см. код в комментариях — и плясать от этого)
в комментариях М.Алексеев поделился еще ссылкой arxiv.org/abs/1608.07936 (опубликовано в AMM) — там объясняется, что если результант свободен от квадратов, то все его делители возникают как значения НОДа
¹ если хочется посчитать это в sage, то синтаксис не совсем очевидный:
f.resultant(g,x)²
R.<x> = PolynomialRing(GF(1968751)); (x^5-5).factor()³ что такие найдутся — понятно, кстати, заранее: p=5k+1, поэтому если хотя бы один корень лежит в поле, то лежат и остальные (и из обращения в 0 результанта какие-то два отличаются на 1); а если x и x+1 — корни в расширении, то из Галуа-инвариантности прибавлять единицу можно к любому корню и сразу противоречие