4
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Why are you checking d's divisibility by $2n(2n+1)-(4n^2+1)$? $\endgroup$ – db2791 Apr 16 '15 at 3:52
  • 3
    $\begingroup$ 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}$. $\endgroup$ – Anurag A Apr 16 '15 at 3:57
9
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.