Question: Prove for all $n \in N$, $\gcd(2n+1,9n+4)=1$

Attempt: I want to use Euclid's Algorithm because it seemed to be easier than what my book was doing which was manually finding the linear combination.

Euclid's Algorithm states that we let $a,b \in N $. By applying the Division Algorithm repeatedly...then $\gcd(a,b) = r_j$ will be the last non-zero remainder. By the Well Ordering Principle, there is a smallest element of the set of natural numbers less than or equal to $r_j$.

I have used long division, but since I can't get it to show up here, I will type what I've done.

Starting at $\gcd(2n+1,9n+4)$,


I can multiply $2n+1$ four times and I would have a remainder of $n$ because $(9n+4)-(8n+4) = 9n+4-8n-4=n$

so we have $4 \cdot (2n+1)+n$ if I apply Euclid's Algorithm.

For $\gcd(2n+1, n)$,


I can multiply $n$ 2 times and I will have only 1 as the remainder because $(2n+1)-(2n+0) = 2n+1-2n+0=1$

Therefore, we have $2 \cdot (n) +1$

and $\gcd(n,1)$ which is $1$

Since the end result is $1, \gcd(2n+1,9n+4)=1$

I followed an example from this link


Am I doing this correctly?

  • $\begingroup$ Your approach looks correct to me (except that you exchanged the numerator and denominator in your first fraction). $\endgroup$ – Peter Košinár Apr 18 '14 at 8:13
  • $\begingroup$ Really? wow I was going on a wing and a prayer...I was trying to manually find a linear combination which my book did, but that was crazy. Then, I remembered solving gcd problems like gcd(158,36) and that involved dividing a lot, so I thought to myself, hmm what if I use the Algorithm for my problem and I got it down to 1. so the fraction on the first should've been $\frac{9n+4}{2n+1}$ $\endgroup$ – usukidoll Apr 18 '14 at 8:15
  • 1
    $\begingroup$ @Martin I don't think it was worth bumping an old question for such a trivial edit. It wasted a few minutes of my time, and probably similarly for others. $\endgroup$ – Gone Dec 21 '16 at 2:39
  • $\begingroup$ I couldn't agree more with @BillDubuque. This question was when I was FIRST started PROOF WRITING!!! $\endgroup$ – usukidoll Dec 21 '16 at 3:54

One approach can be create a relation eliminating $n$ as follows :


If integer $d$ divides $\displaystyle 2n+1,9n+4$ it will divide $S=1$

| cite | improve this answer | |
  • $\begingroup$ what is that? I'm kind of new at that approach. $\endgroup$ – usukidoll Apr 18 '14 at 8:19
  • $\begingroup$ @usukidoll, Please find the edited version $\endgroup$ – lab bhattacharjee Apr 18 '14 at 8:20
  • $\begingroup$ I've read about this in another question... so we need to find an integer $d$ that will divide both $2n+1$ and $9n+4$? $\endgroup$ – usukidoll Apr 18 '14 at 8:22
  • 1
    $\begingroup$ @usukidoll It is proved here that every integer that divides $2n+1$ and $9n+4$ will definitely divide $1$. Well, wich integers do that? I can only think of $-1$ and $1$. The greatest common divisor of $2n+1$ and $9n+4$ divides $2n+1$ and $9n+4$, right? So it must be $1$ or $-1$. It is also demanded to be positive. Well then only one possibility remains: it must equalize $1$. I hope this is enough for you. $\endgroup$ – drhab Apr 18 '14 at 8:37
  • $\begingroup$ yes it is since by theorem 2.5.5 let $a,b, \in Z$ with $a,b$, not both $0$. Then $gcd(a,b)$ is the least positive linear combination of $a$ and $b$. So, by that theorem alone, -1 is clearly not an option. $\endgroup$ – usukidoll Apr 18 '14 at 8:41

It can use this property: $$GCD(a,b)=GCD(a-qb,b) $$ So: $$ GCD(2n+1,9n+4)=GCD(2n+1,n)=GCD(1,n)=1$$

| cite | improve this answer | |

Your approach is quite correct (As far as I think). Here is a similar but still different one.

Suppose that $\gcd(2n+1,9n+4)\ne1$ and there exist a $d$ such that $\gcd(2n+1,9n+4)=d$.

Now $d|9n+4$, and $d|2n+1$ $\implies d|9n+4- 4\times (2n+1)$.

$\implies d|n$.

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

Again: $d|n+1-n\implies d|1$.

It is enough I think.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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