Show that the numbers $(2n + 1)$ and $(4n^2+1)$ are relatively prime How can I show that
$(2n + 1)$ and $(4n^2+1)$
are relatively prime for all $n$?
I know the use of $ax + by = 1$ to show $x,y$ to be relatively prime, but how can I apply that here?
 A: $\,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$
A: 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$.
A: 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$.
A: We will find integers  $x$  and $y$ such that $(2n+1)x+(4n^2+1)y=1$. (This is not the most natural way to prove the coprimality.)
Note that $x_0=-(2n-1)$, $y_0=1$ almost works, except that $(2n+1)x_0+(4n^2+1)y_0=2$. There is an easy fix. For
$$(2n+1)(x_0+4n^2+1)+(4n^2+1)(y_0-(2n+1))=2.$$
Let $x=\frac{x_0+4n^2+1}{2}=2n^2-n+1$ and let $y=\frac{y_0+(-(2n+1))}{2}=-n$. 
A: Let $a = 2n + 1$, and $b + 4n^2 +1$. We wish to show that $\gcd(a,b) = 1$.Suppose that $p$ is a common factor of $a$ and $b$. Then $p$ divides $a^2 = 4n^2 + 4n + 1$, and $p$ divides $b = 4n^2 +1$. Therefore $p$ divides $a^2 - b = 4n$. But $p$ is clearly odd and prime to $4$, so $p$ divides $n$. Then $p$ divides both $n$ and $2n +1$, which are clearly relatively
prime, so we have a contradiction, and $\gcd(a,b) = 1$.    
