# Proof or counter these gcd arguments: [closed]

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

## closed as off-topic by Aqua, Joffan, JMoravitz, Erick Wong, NamasteNov 7 '17 at 1:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Aqua, Joffan, JMoravitz, Erick Wong, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

• Hint: Suppose $d$ is simultaneously a divisor of $2n-1$ as well as $n$. Then this means that $2n-1=kd$ for some integer $k$ as well as..... – JMoravitz Nov 6 '17 at 18:32
• Please show what progress you have made towards an answer, so people will know what level of response will be helpful. – Joffan Nov 6 '17 at 18:32
• @Joffan sorry, I've added details in my edit – tigerustin Nov 6 '17 at 18:41
• You arrived at $d(2l-k)=1$ and so $d$ is a divisor of $1$. What are the possible divisors of $1$? What does that mean $d$ is equal to? What does that mean $\gcd(2n-1,n)$ is equal to? – JMoravitz Nov 6 '17 at 19:09
• @JMoravitz We know $d(2l-k)=1$, so $2l-k=1/d$. We know $l, k, d$ are natural numbers so $d$ must be 1. Correct? – tigerustin Nov 6 '17 at 19:18

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

• Why not just $n=1$? (i.e. OP did absolutely no work to test the hypothesis) – Erick Wong Nov 6 '17 at 18:36
• this better, and simplier, but i like the number $3$ – Dr. Sonnhard Graubner Nov 6 '17 at 18:37
• It is a great number :). – Erick Wong Nov 6 '17 at 18:37
• a prime number and a Erdos number – Dr. Sonnhard Graubner Nov 6 '17 at 18:38
• My favorite use of $3$ has to be its position in front of all other naturals in the total ordering established by Sharkovskii’s theorem. – Erick Wong Nov 6 '17 at 18:41

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

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