Show $4m^2+1$ and $2m+1$ are Co-Prime for integer $m$

Question

Does this mean I need to show that $\gcd(4m^2+1, 2m+1) = 1$ ? If so, how do I do it?

Answer 1

$\gcd(A,B) = \gcd(A \pm kB, B)$

and $(4m^2 + 1)- 2m(2m+1) = -2m+1$

So $\gcd(4m^2 + 1, 2m+1) = \gcd([4m^2 +1] - 2m(2m+1), 2m+1) = \gcd(-2m+1, 2m+1)$.

Can you finish it from there by figuring out what $\gcd(-2m+1, 2m+1)$ is?

If not notice that $(-2m + 1) +(2m+1) = 2$.

And notice that $(2m+1) -2m = 1$.

so can you finish from there?

....

If I wanted to be perverse and obscure I'd point out that

$1 = (2m+1) - [(4m^2 + 1) - 2m(2m+1) + (2m + 1)]*m$.

Does that remind you of anything?

What about

$(2m+1)\cdot (2m^2 - m +1) + (4m^2+1)\cdot(-m)=1$.

Remember Bezout's Lemma?

Answer 2

If $4m^2+1$ and $2m+1$ are divisible by $d$ then $(2m+1)^2 - (4m^2+1) = 4m$ is also divisible by $d$.

Further, $4m - (2m+1) = 2m-1$ is also divisible by $d$, and therefore $(2m+1) - (2m-1) = 2$ is also divisible by $d$. Can you reach the conclusion from here?

Answer 3

The extended Euclidean algorithm gives a denominator (see last line). Just think that $(a+b)(a-b) = a^2 - b^2,$ as in:

$$ \left( 4 x^{2} + 1 \right) - \left( 2 x + 1 \right) \left( 2 x - 1 \right) = 2 $$

==================================================

$$ \left( 4 x^{2} + 1 \right) $$

$$ \left( 2 x + 1 \right) $$

$$ \left( 4 x^{2} + 1 \right) = \left( 2 x + 1 \right) \cdot \color{magenta}{ \left( 2 x - 1 \right) } + \left( 2 \right) $$ $$ \left( 2 x + 1 \right) = \left( 2 \right) \cdot \color{magenta}{ \left( \frac{ 2 x + 1 }{ 2 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( 2 x - 1 \right) } \Longrightarrow \Longrightarrow \frac{ \left( 2 x - 1 \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( \frac{ 2 x + 1 }{ 2 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 4 x^{2} + 1 }{ 2 } \right) }{ \left( \frac{ 2 x + 1 }{ 2 } \right) } $$ $$ \left( 4 x^{2} + 1 \right) \left( \frac{ 1}{2 } \right) - \left( 2 x + 1 \right) \left( \frac{ 2 x - 1 }{ 2 } \right) = \left( 1 \right) $$

Answer 4

Yes, $4m^2+1=(2m+1)(2m-1)+2$, so, if $d$ is a positive divisor of $4m^2+1$ and $2m+1, $

then $d|2$, so $d=1$ or $2$. But $2\nmid 4m^2+1$, so that leaves $d=1$.

Answer 5

Case $\,n=2m\,$ even in: $ $ by Euclid $\overbrace{(\color{#0a0}{n^2+1},\,\color{#c00}{n+1})\, =\, (\color{#0a0}2,n+1)}^{\textstyle \color{#0a0}{f(\color{#c00}n)\equiv f(\color{#c00}{-1})}\,\pmod{\color{#c00}{n\equiv -1}}} = 1$ if $n$ even, $2$ if $n$ odd.