Showing Two Numbers Are Relatively Prime

Date: 08/01/2008 at 06:04:19
From: Jabulani
Subject: show that  21n+4 and 14n+3 are relatively prime. 

Show that for every natural number n, 21n + 4 and 14n + 3 are 
relatively prime. 

Date: 08/01/2008 at 22:11:42
From: Doctor Ali
Subject: Re: show that  21n+4 and 14n+3 are relatively prime.

Hi Jabulani!

Thanks for writing to Dr. Math.

We know that

  GCD(a,b) = GCD(a +/- b , b) = GCD(a , b +/- a)

Where GCD denotes the greatest common divisor.  Are you familiar with
these formulas?

So let's start.  We want to evaluate:

  GCD(21n + 4, 14n + 3) = GCD(21n + 4 - 14n - 3, 14n + 3)
                        = GCD(7n + 1, 14n + 3)
                        = GCD(7n + 1, 14n + 3 - 7n - 1)
                        = GCD(7n + 1, 7n + 2)

Now, we can say that (7n + 1) and (7n + 2) are consecutive integers
and their GCD is one.  You may also continue the process and write

  GCD(7n + 1, 7n + 2) = GCD(7n + 1, 7n + 2 - 7n - 1)
                      = GCD(7n + 1, 1)
                      = 1

Did you get the idea?

Please write back if you still have any difficulties.

- Doctor Ali, The Math Forum
  http://mathforum.org/dr.math/