Why is $gcd(2n-1, 2n^2-1) = 1$?

Question

Why is $$gcd(2n-1, 2n^2-1) = 1$$ ?

My first idea is, that $$2n^2-1 = n^2 + (n-1)(n+1) $$ and $$2n-1 = n + (n-1)$$

But I can't make use of this. This seems to have something to do with polynomials, I gues.

Answer 1

$$gcd(2n-1,2n^2-1)=gcd(2n-1,2n^2-2n)=gcd(2n-1,2n(n-1))=1$$ Because $$gcd(2n-1,2)=gcd(2n-1,n)=gcd(2n-1,n-1)=gcd(n,n-1)=1.$$

Answer 2

Mark $d=gcd(2n-1,2n^2-1)$.

Then $d|2n^2-1$ and $d|2n-1$. From second we get $d|(2n-1)n =2n^2-n$ so $$d|(2n^2-1)-(2n^2-n) =n-1$$ So we have $d|2n-2$ and now we have $$d|(2n-1)-(2n-2) =1$$ and we are done.

Answer 3

Hint: $1=(2n+1)(2n-1)-2(2n^2-1)$

Answer 4

With simple congruences:

Let $d$ be a common divisor. Saying that $d$ divides both $2n-1$ and $2n^2-1$ means $2n\equiv 1 $ and $2n^2\equiv 1 \mod d$.

However $2n^2=(2n)n\equiv 1\cdot n=n$. But then $1\equiv 2n^2\equiv 2\mod d$, and $$1\equiv 2\mod d\iff d=1.$$

Answer 5

Credits to lhf: $$gcd(2n-1, 2n^2-1) = gcd\big(2n-1, (2n-1)(2n+1)-2(2n^2-1)\big) = gcd(2n-1, 1) = 1 $$ since $$ 1=(2n+1)(2n−1)−2(2n²−1)$$