7
$\begingroup$

I am posting this to ask if my proof is correct as I haven't taken number theory in a year and I feel a bit rusty. If it isn't correct, please tell me where I went wrong so I can fix it.

I want to prove that the $\gcd(2n-1,2n+1)=1$ for all $n$.

Using the Euclidean Algorithm, we have that $$ 2n+1=(2n-1)\cdot(1)+2 $$ $$ 2n-1=2(n-1)+1 $$ $$ 2=1\cdot(2)+0 $$ Therefore, $\gcd(2n-1,2n+1)=1$ for all $n$.

$\endgroup$
1
  • 5
    $\begingroup$ It's correct, nothing to fix. $\endgroup$ Nov 14, 2013 at 11:03

2 Answers 2

11
$\begingroup$

Another way: if $d$ divides both $2n-1$ and $2n+1$ then it divides their difference, which is $2$. But $2n-1$ and $2n+1$ are odd and so $d$ cannot be $2$ and must be $1$.

$\endgroup$
1
  • $\begingroup$ I like this a lot actually. I wasn't aware of this rule. +1 $\endgroup$
    – Rocket Man
    Nov 14, 2013 at 11:56
2
$\begingroup$

We can also prove like this :

suppose $gcd(2n-1,2n+1)=a$, then we have $$a|2n-1; a|2n+1$$. So there exists $t_1, t_2$ such that $2n-1=at_1$ and $2n+1=at_2$, so from this two equations we get $$at_1+1=at_2-1 \iff a(t_2-t_1)=2$$. So, $a=1 or 2$, if $a=2$ it contradicts with $a|2n+1$.

So, $a=1$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .