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

• What is the expansion of $(2n+1)^2$? – abiessu Apr 16 '15 at 3:46
• @abiessu how do you prove this question using expasions? – user42912 Apr 16 '15 at 3:50
• Others have covered it, but basically we get to $(2n+1)^2=4n^2+4n+1$. – abiessu Apr 16 '15 at 4:00

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

• Why are you checking d's divisibility by $2n(2n+1)-(4n^2+1)$? – db2791 Apr 16 '15 at 3:52
• I am using the fact that if $d | A$ and $d | B$, then $d$ divides every linear combination of $A$ and $B$, i.e. $d | Ax+By$ for all $x,y \in \mathbb{Z}$. – Anurag A Apr 16 '15 at 3:57

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

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

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