Consider $f(n) = \gcd(1 + 3 n + 3 n^2, 1 + n^3)$
I don't know why but $f(n)$ appears to be periodic. Also $f(n)$ appears to attain a maximum value of $7$ when $n = 5 + 7*k $ for any $k \in \Bbb{Z}$.
Why?
And how would one find this out?
Given two polynomials $p_1(n)$ and $p_2(n)$, how does one calculate the maximum value of $\gcd( p_1(n), p_2(n) ) $ and where this maximum is found?
On
If integer $d$ divides both $1+n^3,1+3n+3n^2$
$d$ must divide $n(1+3n+3n^2)-3(1+n^3)=3n^2+n-3$
$d$ must divide $1+3n+3n^2-(3n^2+n-3)=2n+4$
$d$ must divide $3n(2n+4)-2(1+3n+3n^2)=6n-2$
$d$ must divide $3(2n+4)-(6n-2)=14$
So, $(1+n^3,1+3n+3n^2)$ must divide $14$
Now, $3n^2+3n+1=6\dfrac{n(n+1)}2+1\equiv1\pmod2\implies 3n^2+3n+1$ is odd
So, $(1+n^3,1+3n+3n^2)$ must be $1$ or $7$
Again, $3n^2+3n+1\equiv0\pmod7\iff3(n^2+n-2)\equiv0\iff n^2+n-2\equiv0$ $\iff(n+2)(n-1)\equiv0\iff n\equiv1,-2$
Now, $n\equiv1\implies n^3+1\not\equiv0\pmod7$
and $n\equiv-2\pmod7\implies n^3+1\equiv0$
So, $(1+n^3,1+3n+3n^2)=7$ if $n\equiv-2\pmod7$ else they are co-prime
One cannot blindly run Euclid's algorithm for polynomials, but:
First note that $3n^2+3n+1$ is not a multiple of $3$ for $n\in\mathbb Z$, hence it doesn't change the gcd to multiply the second expression by $3$ and the subtract from $n-1$ times the first expression, i.e. we have $$\begin{align} f(n)&=\gcd(1+3n+3n^2, 3(n^3+1)-(n-1)(1+3n+3n^2))\\&=\gcd(1+3n+3n^2, 2n+4).\end{align}$$ Next, $1+3n+3n^2$ is odd for all $n$, hence casting out the factor of $2$ from $2n+4$ does not alter the gcd, nor does subtracting $3n-3$ times the second expression from the first, i.e. we have $$ \begin{align}f(n)&=\gcd(1+3n+3n^2,n+2)\\&=\gcd((1+3n+3n^2)-(3n-3)(n+2), n+2)\\&=\gcd(7,n+2).\end{align}$$
This last expression is clearly periodic modulo $7$, and is maximal when the gcd equals seven, i.e. for $n\equiv 5\pmod 7$.