GCD of $n^2-3n-1$ and $n-4$ $n$ is a natural number and after trying the division algorithm
$$\gcd(n^2-3n-1,n-4)=\gcd(n-4,n-1)=\gcd(n-1,-3)=\gcd(n-1,3)$$
For the last part I'm not sure whether it does equal to $\gcd(n-1,3)$.
If yes, then should I take the cases where $n$ is $3k+i, 0\le i\le2$?

Using this implementation of the Extended Euclidean Algorithm, rotated $90^{\large\circ}$ and applied to polynomials, gives
$$
\begin{array}{c|c|c}
\color{#00F}{n^2-3n-1}&1&0\\
\color{#00F}{n-4}&0&1\\
\color{#090}{n-1}&\color{#C00}{1}&\color{#C00}{-n}&n\\
\color{#090}{-3}&\color{#C00}{-1}&\color{#C00}{n+1}&1
\end{array}
$$
which says that
$$
\overbrace{\begin{bmatrix}
\color{#C00}{1}&\color{#C00}{-n}\\\color{#C00}{-1}&\color{#C00}{n+1}
\end{bmatrix}}^{\det=1}
\begin{bmatrix}
\color{#00F}{n^2-3n-1}\\\color{#00F}{n-4}
\end{bmatrix}
=\begin{bmatrix}
\color{#090}{n-1}\\\color{#090}{-3}
\end{bmatrix}
$$
which means any integer linear combination of $n-1$ and $3$ is an integer linear combination of $n^2-3n-1$ and $n-4$ and vice-versa (since the determinant of the matrix is $1$). This means that
$$
\gcd\left(n^2-3n-1,n-4\right)=\gcd(n-1,3)
$$
