What is the highest common factor of $n$ and $2n + 1$

Question

I am trying to find the highest common factor of $n$ and $2n + 1$, but I am not sure how to go about it, perhaps it is clear that the $lcm(2n+1, n)$ is $n(2n+1)$ and from this we can get the $hcf$ as 1, but I am not sure if that is a good enough argument.

Thanks!

Answer 1

Note that if $d=\gcd(n,2n+1)$, then d divides $n$ and $2n+1$, and so d divides $(2n+1)-2n=1$. Therefore, $d=1$.

In particular, since $ab=\gcd(a,b)\cdot lcm(a,b)$, you have that $$lcm(2n+1,n)=n(2n+1).$$

Answer 2

In general if $m$ divides $a$ and $b,$ then $m$ divides $ax+by$ for any integers $x,y.$ Because there are integers $u,v$ with $a=mu$ and $b=mv,$ so $ax+by=(mu)x+(mv)y=m(ux+vy)$ is an integer-multiple of $m.$

So if $m$ divides $n$ and $2n+1,$ then $m$ divides $(n)(-2)+(2n+1)(1)=1.$

For $a,b\in \mathbb N$ we have $ab=\gcd(a,b)\cdot$ lcm$ (a,b).$ So lcm $(a,b)=ab$ iff $\gcd (a,b)=1.$ But how would you prove that lcm$(n,2n+1)=n(2n+1)$ without assuming that $\gcd (n,2n+1)=1$?