# Help w/ Euclidean Rings and P.I.D.s

• Jan 31st 2008, 03:28 PM
Pyrrhus
Help w/ Euclidean Rings and P.I.D.s
Hey, I have two questions I need some help with because I missed my recitation. Answers are fine, but I'd prefer it if someone could just tell me the procedure/give me a nudge in the right direction.

The first is: Suppose that in the Euclidean Algorithm for finding the gcd of two integers "a" and "b" we always choose "q" and "r" so a=bq+r and 0 = or < r < b. How many applications of the division algorithm are needed to find the gcd of F(n) and F(n+1) in where F is the fibonnaci sequence and F(0)=1. What is this gcd?

And the second: Show that if R is a Principal Ideal Domain and D is a multiplicatively closed subset of R, then (D^-1)R is a Principal Ideal Domain.

• Jan 31st 2008, 07:43 PM
ThePerfectHacker
Quote:

Originally Posted by Pyrrhus
The first is: Suppose that in the Euclidean Algorithm for finding the gcd of two integers "a" and "b" we always choose "q" and "r" so a=bq+r and 0 = or < r < b. How many applications of the division algorithm are needed to find the gcd of F(n) and F(n+1) in where F is the fibonnaci sequence and F(0)=1. What is this gcd?

$F(n+1) = F(n)+F(n-1)$
$F(n) = F(n-1)+F(n-2)$
$F(n-1) = F(n-2)+F(n-3)$
...
So what do you think it is?

Quote:

And the second: Show that if R is a Principal Ideal Domain and D is a multiplicatively closed subset of R, then (D^-1)R is a Principal Ideal Domain.
Define what $D^{-1}$ means. And what does the juxaposition $D^{-1} R$ mean?
• Jan 31st 2008, 10:06 PM
Pyrrhus
It's like a limited fraction field. (D^-1)R is the extension of R such that all the elements of D in R have multiplicative inverses in (D^-1)R. So all elements r of R get mapped to (r/1), and all elements mapped from d of D in R of the form (d/1) have an inverse in the latter ring of the form (1/d). For example, if you take R=Z and D=multiples of 3 in Z, (D^-1)R is the ring whose elements are of the formg (a/b) where "a" is an element of Z and "b" is an element of Z that is a multiple of 3.

Also, I got the answer to the first one a few hours ago so I just need to work on the second. :D