Tips finding the gcd of $(n^2-3n-1, n-4)$

Question

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

Answer 1

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$.

Answer 2

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$$

Answer 3

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$$