Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
Question and Answer together !!!. – Felix Marin Mar 25 '14 at 7:10
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|cite|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
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$.

share|cite|improve this answer

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


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

share|cite|improve this answer

Your Answer


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.