Show that the numbers $(2n + 1)$ and $(4n^2+1)$ are relatively prime

Suppose $d$ is a common divisor of these numbers, then $d | 2n(2n+1)-(4n^2+1)=2n-1$. But then $d | (2n+1)-(2n-1)=2$. So $d$ is either $1$ or $2$. But both $2n+1$ and $4n^2+1$ are odd so $d$ has to be $1$.

There are more inspired ways to attack this example, but when we're feeling unimaginative we can fall back to the general method of Euclid's algorithm:

$$\gcd(4n^2+1, 2n+1)$$

Divide $4n^2+1$ by $2n+1$ to get quotient $2n-1$ and remainder $2$:

$$ = \gcd((2n-1)(2n+1) +2, 2n+1)$$

Turn the handle on Euclid's algorithm:

$$ = \gcd(2, 2n+1)$$

Now, we could divide $2n+1$ by $2$ to get quotient $n$ and remainder $1$, but at this point any fule kno that $2n+1$ is odd, so:

$$ = 1$$

This shows they are relatively prime.

---

You want to find $a, b$ such that $ax + by = 1$, and by using the divisions we performed in following Euclid's algorithm we can do that. We learned:

$$ 1 = (2n + 1) - n (2)$$ $$ 2 = (4n^2 + 1) - (2n-1)(2n+1)$$

That is with $x = 2n+1$ and $y = 4n^2+1$:

$$ 1 = x - n(2)$$ $$ 2 = y - (2n-1)x$$

Substituting the second into the first:

$$ 1 = x - n( y - (2n-1)x )$$ $$ = (1 + n(2n-1))x - n y$$ $$ = (2n^2-n+1)x - n y$$

So the coefficients you need are $2n^2 - n + 1$ and $-n$.

$\,d\mid \color{#c00}{a^2\!+\!1,a\!+\!1}\,\Rightarrow\,d\mid 2 = \color{#c00}{a^2\!+\!1}\!-\!\overbrace{(\color{#c00}{a\!+\!1})(a\!-\!1)}^{\Large a^2\ -\ 1},\,$ so $\,d=1\,$ if $\,a =2n\,$ $(\Rightarrow$ $\,a\!+\!1\,$ is odd)

${\bf Remark}\ \ (b,a)\, =\, (b\bmod a,\,a)\ $ by Euclid so more generally

$\quad\ \ (f(a),\,a\!+\!1)\, =\, (f(-1),\,a\!+\!1)\,\ $ by $\! \underbrace{f(-1)\, =\, f(x)\bmod x\!+\!1}_{\large \text{Polynomial Remainder Theorem}}$

Above $\,f(x)=x^2\!+\!1\,$ so $\,f(-1) = 2$