$\gcd(4n+1, n+2)$ is found in what sense?

Question

What is the gcd of these two numbers? Is it possible to find the gcd? It should be $1$ when $n=1$, but $3$ when $n=5$.

$4n+1 = (3)(n+2) + (n-5)$ <-- This step is only valid when $n \geq 5$

How do I find the gcd?

Answer 1

Hint $\ $ By Euclid $\,\gcd(n\!+\!2,4\color{#c00}n\!+\!1) = \gcd(n\!+\!2,\, 4(\color{#c00}{-2})\!+\!1)\,$ since $\ \color{#c00}{n\equiv -2}\pmod{\!n\!+\!2}$

---

Similarly we have $\ \gcd(n\!-\!a,f(n)) = \gcd(n\!-\!a,f(a))\ $ for any polynomial $f(x)$ with integer coef's which follows by employing the following congruence rule (follow the link for a proof).

Polynomial Congruence Rule $\ $ If $\,f(x)\,$ is polynomial with integer coefficients then $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$

Note how simple the proof is when viewed this way - it amounts to simple polynomial evaluation.

This is a prototypical example of the power of congruence arithmetic. It allows us to replace obscure manipulation of divisibility relations by simpler congruence operations and equations, which allows reuse of our well-honed intuition on analogous integer arithmetic. The common structure in both arithmetics is abstracted out when one goes on to study (quotient) rings.

Answer 2

The gcd divides $4n +1 - 4 (n+2) = -7$, so it can only be $1$ or $7$. If $7$ divides $n+2$, then $n \equiv -2 \pmod{7}$, so $4 n + 1 \equiv -8 + 1 \equiv 0 \pmod{7}$.

Thus the gdc is $7$ when $n \equiv -2 \pmod{7}$, and $1$ otherwise.

Answer 3

Since $4\cdot(n+2)+(-1)\cdot(4n+1)=7$, we can say that either $\gcd(4n+1,n+2)=1$ or $\gcd(4n+1,n+2)=7$. Both cases can happen: for $n=1$ the gcd is $1$, for $n=5$ the gcd is $7$.

Answer 4

If integer $d$ divides both $n+2,4n+1, d$ must divide $4(n+2)-(4n+1)=7$

Clearly $7|(n+2)\iff7|(4n+1)$

Now $7|(n+2)\iff n\equiv-2\pmod7\equiv5$