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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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