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
Harrison W.
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

Comments

  • Harrison W.
    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
      JMoravitz almost 7 years
      Hint: Euclidean division algorithm
    • barak manos
      barak manos almost 7 years
      Isn't it the same as GCD? (in which case, the answer is obviously $1$).
    • TonyK
      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.
      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.