Tips finding the gcd of $(n^2-3n-1, n-4)$ 
I need tips on how to find the $gcd(n^2-3n-1, n-4)$ for any $n \in \mathbb{N}$.
I tried the two following methods (but got stuck):

Since I need to find the $gcd(n^2-3n-1, n-4)$, then there is a $q \in \mathbb{Z}$ which is the divisor of both $(n^3-3n-1)$ and $(n-4)$, giving each of them an answer of $q_1,q_2 ∈ \mathbb{Z}$ accordingly,
therefore, it is possible to write them as follow:
$n^2-3n-1 = q*q_1$
$n-4 = q*q_2$
Because $q,q_1,q_2 ∈ \mathbb{Z}$, multiplying them with each other produces another Integer (same with adding to them an Integer), so
$n^2-3n = q_3$ , $q_3 ∈ \mathbb{Z}$
$n = q_4$ , $q_4 ∈ \mathbb{Z}$
With this method, I got stuck here (didn't find a way how to continue).

Another method I've tried is:
According to the Euclidean Algorithm,
$n^2-3n-1 = (n-4)*q + r, q,r ∈ \mathbb{Z}$
Use $q=n$,
$n^2-3n-1 = (n-4)*n+r$ => $n-1=r$
$n^2-4n=(n-1)q+r$ (while $q=n$) => $-3n=r$
$n^2-n=-3n*n+r$ => $4n^2-n=4$
and so on...but also got stuck..
I'd appreciate any tips on how to continue with what I've tried or if I should try a different approach
 A: hint
Use this
$$b=aq+\color{red}{r}\implies \;gcd(a,b)=\;gcd(a,\color{red}{r})$$
with
$$b=n^2-3n-1=n(n-4)+n-1$$
$$=(n+1)(n-4)+\color{red}{3}$$
So,
$$gcd(n^2-3n-1,n-4)=gcd(n-4,3)$$
$$=gcd(n+2,3)=G$$
Thus
$$n\equiv 0\mod 3 \implies G=1$$
$$n\equiv 1 \mod 3\implies G=3$$
$$n\equiv 2\mod 3 \implies G=1$$
A: Suppose $d=(n^2-3n-1,n-4)$ so $$d|n^2-3n-1\\d|n-4$$
from $d|n-4 \to d|(n-4)(n+1)$ so
$$d|n^2-3n-4$$
and now $$d|A,d|B \to d|rA+sB \\d|(n^2-3n-1)-(n^2-3n-4) \to d|3\\
d=1,or,3$$
A: Bear in mind that $\gcd(a,b) = \gcd(a\pm kb, b)$ for all integers $k$.
So if $n^3 - 3n -1 = P(n)(n-4) + R(n)$ then $\gcd(n^2 -3n-1, n-4) = \gcd(n^2-3n-1 -P(n)(n-4), n-r) = \gcd(R(n), n-4)$.
And if we use synthetic division
$n^2   -3n -1 = n^2(n-4) +4n -3n -1=$
$n(n-4) +n-1=$
$n(n-4) +(n-4) +4-1=$
$n(n-4) + (n-4) + 3=$
$(n +1)(n-4) + 3$.
....
So $\gcd(n^2-3n-1,n-4)= \gcd((n+1)(n-4) + 3, n-4)=\gcd(3,n-4)=\gcd(3,n-4 +3)=\gcd(3,n-1)$.
So if $3|n-1$ or in other words if $n\equiv 1 \pmod 3$ then $\gcd(n^2-3n-1,n-4)=\gcd(3,n-1)=3$.
ANd if $3\not \mid n-1$ or in other words if $n\not \equiv 1$ or if $n\equiv 0, 2 \pmod 3$ and $n-1\equiv 2,1$ and $n-1$ and $3$ are relatively prime then $\gcd(n^2-3n-1,n-4)=\gcd(3,n-1)=1$.
