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

1,313

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

Share:
1,313
Author by

### Harrison W.

I am a PhD candidate in Statistics. Interested in Bayesian Statistics and ethical Machine Learning theory and applications.

Updated on December 06, 2022

• Harrison W. 11 months

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!

• JMoravitz almost 7 years
Hint: Euclidean division algorithm
• barak manos almost 7 years
Isn't it the same as GCD? (in which case, the answer is obviously $1$).
• TonyK almost 7 years
Why is it clear that lcm$(2n+1,n)=n(2n+1)$? This is correct, but it seems exactly as difficult as showing that hcf$(n,2n+1)=1$.
• Harrison W. almost 7 years
@TonyK that's why I said perhaps, I wasn't sure if one was more intuitively correct than the other, apparently not.