find $\gcd(2n+1,n)$ assuming that $n$ is non negative integer

Question

Should I use the rule $$n=(2n+1)\cdot q+r$$ I am not sure how to find the gcd while $n$ is unknown or should I assume that the numbers will be odd so the gcd will be $1$?

Answer 1

Your solution is correct (except for an arithmetic error - $2n+1=a t_1$ and $n = at_2$ means that $2at_1+1=a t_2$). But your conclusion holds.

Answer 2

You could use the Eucledean algorithm, where you actually would get the "last line" of the algorithm straight up which shows that the "last nonzero remainder" is $1$, so the $GCD$ is $1$. For $\gcd(2n+1,n)$

$$ 2n+1=2\cdot n +1 $$ $$ n=1\cdot n +0. $$

---

EDIT after comment:

Try to read up on the wiki link I put in my answer, but I take two concrete examples here.

Say you would like to find $\gcd(30,7)$, according to the algorithm you would write:

$$ 30=7\cdot4 +2 $$ $$ 7=3\cdot 2 +1 $$ $$ 3=3\cdot 1+0 $$

In the last row the remaider is $0$ so the last nonzero remainder is $1$ therefore $\gcd(30,7)=1$

Say you would like to find $\gcd(40, 12)$ then you would write

$$ 40=3\cdot 12 +4 $$ $$ 12=3\cdot 4+0 $$

The last nonzero remainder is $4$ therefore $\gcd(40,12)=4$

Eventually you can look at this as well.