Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/