0

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$?

Vinyl_cape_jawa
  • 4,794
geektobe
  • 39
  • I try to solve it this way suppose gcd(2n+1,n)=a, then we have a|2n+1;a|n . So there exists t1,t2 such that 2n+1=at1 and n=at2, so from this two equations we get at1+1=at2⟺a(t2−t1)=1 . So, a=1 – geektobe Oct 09 '19 at 20:00
  • 1
    Notice that if $d$ is a common divisor of $n$, $2n+1$, then it is also common divisor of $2n, 2n+1$. Hence it is a common divisor of $1=(2n+1)-2n$. What can we conclude? – MathematicsStudent1122 Oct 09 '19 at 21:29
  • You made things difficult by trying to divide $n$ by $2n+1$. It will be easier to apply the division algorithm (quotient and remainder) for $2n+1$ divided by $n$. – hardmath Oct 09 '19 at 21:35
  • 1
    The remarkable thing is that you can Euclid's algorithm to find this gcd, even with $n$ being unknown! –  Oct 10 '19 at 07:59
  • @ Hurky can you explain ? – geektobe Oct 10 '19 at 08:01

2 Answers2

0

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.

rogerl
  • 22,399
0

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.

Vinyl_cape_jawa
  • 4,794