Associated Topics || Dr. Math Home || Search Dr. Math

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!

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.
```
Associated Topics:
College Modern Algebra

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search