Proof or counter these gcd arguments:

Question

(a) For all positive integers $n$, we have gcd$(2n−1, n) = 1$.

For this, first I tried the Euclidean Algorithm. I divided $2n-1$ by $n$, and got $n-(1/n)$. Then, I didn't know what to do with $1/n$.

I also tried expressing them by a multiple. Say the gcd of them is $d$, so $2n-1=dk$ and $n=dl$ for natural numbers $k,l$. I eventually arrived at $d(2l-k)=1$, and didn't know what to do.

(b) For all positive integers $n$, we have gcd$(4n−2, n) = 2$.

*(b) is solved.

Answer 1

b) is wrong, take $n=3$ then we get $$\gcd(10;3)=1$$

Answer 2

For non-zero integers $a,b$ and integer $c$ we have $$\gcd (a,b)=\gcd (a-bc,b).$$ Proof: For integer $d\ne 0$ we have

(i). If $d|a$ and $d|b$ then $d|(a-bc)$. Because $a/d,b/d\in \Bbb Z$ so $(a-bc)/d=(a/d)-(b/d)c\in \Bbb Z.$

(ii).If $d|(a-bc)$ and $d|b$ then $d|a$. Because $(a-bc)/d, b/d\in \Bbb Z$ so $a/d=((a-bc)+bc)/d=(a-bc)/d+(b/d)c\in \Bbb Z.$

With $a=2n-1, b=n, c=2$ we have $\gcd (2n-1,n)=\gcd ((2n-1)-2n, n)=\gcd (-1,n).$ The only divisors of $-1$ are $\pm 1$ and the larger divisor $+1$ divides every $n\in \Bbb Z.$ So $\gcd(-1,n)=1.$

Answer 3

For a), $\gcd(2n-1,n) = \gcd((2n-1-n),n) = \gcd(n-1,n) = 1$ for any consecutive numbers.

For b), $\gcd(4n-2,n) = \gcd(4n-2-3n,n) = \gcd(n-2,n) = \gcd(n,2)$. This could be either $2$ or $1$, depending on the parity of $n$.