Showing Two Numbers Are Relatively PrimeDate: 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: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/