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$?
 A: *

*If you write as follows $$\gcd(n-4, n-1) = \gcd(n-4, 3) = \gcd(n-1, 3)$$ you will be sure i.e


*

*$n-1 - (n-4) = 3$

*$n-4 + 3 = n-1$


*Yes, you can see those cases.

A: After help from the comments and @VIVID.
$$\gcd(n^2-3n-1,n-4)=\gcd(n-4,n-1)=\gcd(n-1,-3)=\gcd(n-1,3)$$
The cases of $n$ are $n=3k,n=3k+1,n=3k+2$ for a natural $k$, will be:
$n=3k \Rightarrow \gcd(3k-1,3)=1$
$n=3k+1 \Rightarrow \gcd(3k,3)=3$
$n=3k+2 \Rightarrow \gcd(3k+1,3)=1$
A: 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)
$$
