Abstract Algebra GCD Proof Using Ideals

Date: 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.