Abstract Algebra GCD Proof Using IdealsDate: 06/28/2005 at 23:25:01 From: Joshua Subject: A discrete math (or maybe abstract algebra) question Is this formula true? GCD(an + b, a(n+1) + b) = GCD(a, b) I can't write a clear proof where I know all the assumptions I make are true. For example, I can't remember several of the identities involving the "divides" operator. I'm thinking that a(n+k) + b can be rewritten as A(n+1) + B (A = ak, B = an - akn + b). Date: 06/29/2005 at 19:41:09 From: Doctor Vogler Subject: Re: A discrete math (or maybe abstract algebra) question Hi Joshua, Thanks for writing to Dr. Math. Some useful properties of GCD are GCD(x, y) = GCD(x, x + y) = GCD(x, nx + y) and you can use both of these to prove your claim. In fact, it is even easier to think of GCD in terms of ideals. Have you dealt with ideals of rings in abstract algebra? If so, consider the ring of integers, and instead of GCD(x, y) think "the ideal generated by x and y." That means that it includes every number of the form nx + my for integers m and n. The GCD is the smallest positive number in this set; that is, every number in this set is a multiple of the GCD. Showing that two GCDs are the same is equivalent to showing that the two ideals are the same. For example, to show GCD(an + b, a(n+1) + b) = GCD(a, b) it is equivalent to show that the ideals (an + b, a(n+1) + b) = (a, b) are the same set of numbers. Remember that the ideal generated by two numbers is the smallest ideal containing those two numbers. Clearly both an+b and a(n+1)+b are in the ideal on the right, which means that the ideal on the right must contain the ideal on the left (i.e. the left side is a subset of the right side). For the other direction, we need to show that the numbers a and b are in the ideal on the left. Well, subtract the two generators on the left, and you get a. Terrific! We're already halfway done. Then since a is in the ideal, so is an, and then we can subtract this from the first generator, and that gives us b. So we're done! If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 06/29/2005 at 20:27:04 From: Joshua Subject: Thank you (A discrete math (or maybe abstract algebra) question) Thanks for the answer. That cleared everything up. I may have dealt with ideals before, but if I have, I'd forgotten about them. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/