Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search