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).$$
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, 2022Comments

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 yearsHint: Euclidean division algorithm

barak manos almost 7 yearsIsn't it the same as GCD? (in which case, the answer is obviously $1$).

TonyK almost 7 yearsWhy 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.
