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

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)$,

$\frac{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)$,

$\frac{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

http://cms.math.ca/crux/v33/n5/public_page274-276.pdf

Am I doing this correctly?

• Your approach looks correct to me (except that you exchanged the numerator and denominator in your first fraction). – Peter Košinár Apr 18 '14 at 8:13
• 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}$ – usukidoll Apr 18 '14 at 8:15
• @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. – Bill Dubuque Dec 21 '16 at 2:39
• I couldn't agree more with @BillDubuque. This question was when I was FIRST started PROOF WRITING!!! – usukidoll Dec 21 '16 at 3:54

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

$$S=9(2n+1)-2(9n+4)=1$$

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

• what is that? I'm kind of new at that approach. – usukidoll Apr 18 '14 at 8:19
• @usukidoll, Please find the edited version – lab bhattacharjee Apr 18 '14 at 8:20
• 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$? – usukidoll Apr 18 '14 at 8:22
• @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. – drhab Apr 18 '14 at 8:37
• 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. – 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$$

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.