Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
5  
It's correct, nothing to fix. –  Daniel Fischer Nov 14 '13 at 11:03
    
Thanks a lot! +1 –  AJ Stas Nov 14 '13 at 11:04

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer
    
I like this a lot actually. I wasn't aware of this rule. +1 –  AJ Stas Nov 14 '13 at 11:56

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.