The GCD of $(n^2, 2n +1)$

Question

$\text{GCD}(n^2,2n+1)$

I think I need to use the Euclidean algorithm but $n^2 = (2n+1)(1/2n -1/4)+1/4$ so I have no idea how to get the GCD (the remainder is a fraction).

n is a natural number

Answer 1

Note that $2n+1$ is always odd, so $\gcd(n^2,2n+1)=\gcd(4n^2,2n+1)$,

and $4n^2-(2n+1)(2n-1)=1$.

Answer 2

$gc(n^2, 2n+1)$ divides $n(2n+1)-2n^2=n$, it divides $2n+1-2n=1$ so it is $1$

Answer 3

The last nonzero remainder is

$\text{GCD}(x^2,2x+1)=1$

The GCD can be expressed as an integral linear combination of $x^2$ and $2x+1$

$(4)(x^2)+(−2x+1)(2x+1)=1$

Answer 4

The answer is $\gcd(n^2, 2n+1) =1$.

Let $m = \gcd(n^2,2n+1)$. Suppose $m >1$. Then for each prime $p$ that divides $m$ [now $p$ may be 2], $p$ divides both $n^2$ and $2n+1$. So to show that $\gcd(n^2, 2n+1)=1$ it suffices to show that every prime that divides $n^2$ does not divide $2n+1$. We do this below.

Note that if a prime $p$ divides $n^2$ then it also divides $2n$. Which implies that $p$ does not divide $2n+1$ [make sure you see this]. So every prime $p$ that divides $n^2$, does not divide $2n+1$.

Answer 5

$$\gcd(n^2, 2n+1 ) = \gcd(n^2, n^2 + 2n + 1 ) = \left[ \gcd ( n, n+1) \right]^2 = 1^2 = 1.$$