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.

Is this a valid proof for (2n+1,3n+1)=1?

$\exists \ d \in \mathbb{Z}$

  1. $d | 2n+1$ means $2n+1 \equiv 0$ (mod $d$)
  2. $d | 3n+1$ means $3n+1 \equiv 0$ (mod $d$)

Multiply 1. by $3$ and 2. by $2$:

$6n+3 \equiv 0$ (mod $d$)

$6n+2 \equiv 0$ (mod $d$)

Subtract the second from the first to get: $ 1 \equiv 0$ (mod $d$), which means $d|1$, which means $d=1$.

Thanks!

share|improve this question
    
Question and Answer together !!!. –  Felix Marin Mar 25 at 7:10

3 Answers 3

up vote 4 down vote accepted

Yes, nice job! That's a very nice application of the method that I described in your prior question. Notice again how simple the problem becomes once it is reduced to equational (congruence) form.

share|improve this answer
    
Thanks for explaining it! It just clicked, so I hope this will be useful in the future! –  Christoph Mar 8 '11 at 2:35
1  
Yes, learning to effectively work with congruences (i.e. equations in quotient structures) will prove quite useful in your future studies. The sooner you master such the sooner you can make trivial nonessential components of proofs so that you can better focus on the conceptual essence of the matter. When Gauss first introduced congruences they led to breakthroughs in number theory. You'll see analogous breakthroughs once you master them. –  Bill Dubuque Mar 8 '11 at 2:40

Suppose $d$ is a positive integer dividing both $2n+1$ and $3n+1$.
$d$ also dividing $3(2n+1)$ and $2(3n+1)$.
$d$ dividing $(6n+3)-(6n+2)=1$.
$d$ dividing $1$.
$d=1$

share|improve this answer

Very good proof. Another very elementary proof is to use the Euclidean algorithm:

GCD(3n+1,2n+1)=
GCD(3n+1-(2n+1),2n+1)=
GCD(n,2n+1)=
GCD(n,2n+1-n)=
GCD(n,n+1)=
GCD(n,n+1-n)=
GCD(n,1)=1

where I repeatedly subtracted the smaller from the bigger until I got something I could evaluate.

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.