# Valid proof for $(2n+1,3n+1)=1$?

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!

-
Question and Answer together !!!. –  Felix Marin Mar 25 '14 at 7:10

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.

-
Thanks for explaining it! It just clicked, so I hope this will be useful in the future! –  Christoph Mar 8 '11 at 2:35
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$

-

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.

-