10
$\begingroup$

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!

  • 1
    Question and Answer together !!!.2014-03-25

4 Answers 4

6

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.

  • 2
    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.2011-03-08
2

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$

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.

-1

@Bill has already commented on the truth of your proof, here is another one.

Suppose that $(2n+1,3n+1)=d$.

$d|3n+1, d|2n=1$

$d|3n+1-(2n+1)\implies d|n\implies d|2n$

$d|2n+1-2n\implies d|1\implies d=1$