# G.c.d.'s and PID's

#### *melinda*

1. Homework Statement

Prove: If a, b are nonzero elements in a PID, then there are elements s, t in the domain such that sa + tb = g.c.d.(a,b).

2. Homework Equations

g.c.d.(a,b) = sa + tb if sa + tb is an element of the domain such that,
(i) (sa + tb)|a and (sa + tb)|b and
(ii) If f|a and f|b then f|(sa + tb)

3. The Attempt at a Solution

Since a, b, s, t, are all elements of the PID, so is sa + tb by properties of rings.

I also know that if f|a and f|b then a = xf and b = yf. So f|(sa + tb) can be written as f|(sx + ty)f, which shows that f|(sa + tb) as desired.

I'm just not sure how to satisfy criteria (i) of the definition of g.c.d.

I know that if d and d' are g.c.d.'s of a and b, then d and d' are associates, but I'm not sure how to use this to my advantage.

Any suggestions would be appreciated!

Related Calculus and Beyond Homework Help News on Phys.org

#### Hurkyl

Staff Emeritus
Science Advisor
Gold Member
You don't seem to have invoked the fact you are in a PID, rather than in an arbitrary ring...

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving