GCD of $n^2-3n-1$ and $n-4$

Question

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

Answer 1

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

2. Yes, you can see those cases.

Answer 2

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$

Answer 3

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