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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.