Showing elements of a Principal Ideal Domain are Relatively Prime?

[robertjordan]

Homework Statement

Let $R$ be a PID and let $\pi\in{R}$ be an irreducible element. If $B\in{R}$ and $\pi\not{|}B$, prove $\pi$ and $B$ are relatively prime.

Homework Equations

$\pi$ being irreducible means for any $a,b\in{R}$ such that $ab=\pi$, one of #a# and #b# must be a unit (meaning they have multiplicative inverses).

$\pi$ and $B$ being relatively prime means their GCD is the identity element of R (call it 1).

My book also has a theorem saying if $\alpha$ is an irreducible element in a PID and $\alpha|xy$ then $\alpha|x$ or $\alpha|y$.

The reason I am wary to use this is because they cited the problem I'm currently asking about in their proof...

The Attempt at a Solution

EDIT EDIT EDIT: What I had below was wrong (see post 7 if you want to see what I had and why it's wrong). So I'm still very much stuck :(

 

[robertjordan]

Oh and I forgot to add, $R$ being a PID (principle ideal domain) means $R$ is a domain and every ideal in $R$ is a principle ideal.

$R$ being a domain means $R$ is a commutative ring (rings have an identity in my book, so even integers is not considered a ring) that has the cancellation property (ab=ac, a=\=0 implies b=c).

And ideal of $R$ is a subset $I$ of $R$ that has the properties:
(i)$0\in{I}$
(ii)$a,b\in{I}$ implies $(a+b)\in{I}$
(iii)$a\in{I}$ and $r\in{R}$ implies $ar\in{I}$

A ideal $I$ is a principle ideal if there exists and element $b\in{I}$ such that for every element $x\in{I}$ there is an element $k\in{R}$ such that $kb=x$.

 

[STEMucator]

In ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R. ( Wiki : Principal ideal ).

As for your question though. How about... contradiction! Assume $\pi$ and $B$ are not relatively prime ( i.e $gcd(\pi,B) ≠ 1$ ) ...

 

[robertjordan]

In ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R. ( Wiki : Principal ideal ).

As for your question though. How about... contradiction! Assume $\pi$ and $B$ are not relatively prime ( i.e $gcd(\pi,B) ≠ 1$ ) ...

By a theorem in my book, $gcd(\pi,B) ≠ 1$ implies there do not exist $\sigma,\tau\in{R}$ such that $1=\sigma(\pi)+\tau(B)$.

Assume BWOC that $gcd(\pi,B) = d$ for some $d\ne{1}$. Well then $d|\pi$ and $d|B$, so $\exists{k,t}\in{R}$ s.t. $dt=\pi$ and $dk=B$. $dt=\pi$ implies either $d$ or $t$ is a unit (has a multiplicative inverse).

Don't know what to do now..

 

[micromass]

Here's how I would do this for natural numbers...

Let $d\in{\mathbb{N}}$ be an arbitrary divisor of both $\pi$ and $B$. Then we can say $\pi=dk$ and $B=dt$ where $k$ and $t$ are just some integers. This means $\pi\cdot{t}=Bk$. Since $\pi\not{|}B$, we know $\pi|k$, but that means $k|pi$ and $pi|k$. This implies $k=\pi$, so in order for $\pi=dk$ to be valid we need $d=1$. And we're done...

Why not just do the same proof in your case? What if you try to use this proof? Is there something that doesn't work?

 

[robertjordan]

Why not just do the same proof in your case? What if you try to use this proof? Is there something that doesn't work?

One problem is in my book, the proof of this statement for PID's...

Since $\pi\not{|}B$, we know $\pi|k$

... uses the theorem that this post is about.
Another problem is...

$k|\pi$ and $\pi|k$. This implies $k=\pi$

...I don't know if this is necessarily true in general for PID's. Because$k|\pi$ implies $kt=\pi$ for some $t\in{R}$, and $\pi|k$ implies $\pi{q}=k$ for some $q\in{R}$.
Plugging in $kt$ in place of $\pi$, we get $ktq=k$ and since we're in a domain we have cancellation so this implies $tq=1$ but that just means $t$ and $q$ are units that are each other's multiplicative inverse... But that doesn't mean $kt=\pi$ implies $k=\pi$.
So all in all, I'd rather have a smoother proof that doesn't require citing results that were proved using this very result

 

[robertjordan]

Alright how is this...Assume BWOC that $gcd(\pi,B)=d\ne{1}$
Then by the theorem I mentioned in post #4, there do not exist $x,y\in{R}$ such that $1=x{\pi}+y{B}$.Since $\pi$ is irreducible, $d|\pi$ implies $d$ is either a unit (has multiplicative inverse), or is a multiple of $\pi$. (I can prove that statement pretty easily but I don't feel like typing it).

But we're given that $\pi\not{|}B$ so if $d|B$ then $d$ can't be a multiple of $pi$. This means $d$ is a unit.

So by the theorem from my book mentioned in post #4, There exist $\sigma,\tau\in{R}$ such that $d=\sigma{\pi}+\tau{B}$.
But since $d$ is a unit, we can multiply that whole expression by $d^{-1}$ to get $1=(\sigma{d^{-1}}){\pi}+(\tau{d^{-1}}){B}$

These elements $(\sigma{d^{-1}}),(\tau{d^{-1}})$ which we know are in $R$ by closure under multiplication, contradict our initial assumption that:

"there do not exist $x,y\in{R}$ such that $1=x{\pi}+y{B}$."

EDIT EDIT EDIT:

I just found a mistake with the above: the theorem from my book says "if $gcd(a,b)=\delta$ then there exists $x,y\in{R}$ such that $\delta=ax+by$."

So the problem with the above proof is I tried to say "if $gcd(a,b)\ne{\delta}$ then there do not exist $x,y\in{R}$ such that $\delta=ax+by$."
Clearly this is not true in general.
So I'm still stuck :(

 

[Dick]

So I'm still stuck :(

Try and take a direct approach. g=gcd(π,B) is defined to be the generator of the ideal generated by π and B. So?

 

[robertjordan]

Try and take a direct approach. g=gcd(π,B) is defined to be the generator of the ideal generated by π and B. So?

The ideal $(\pi,B)=\{\pi{x}+By : x,y\in{R}\}$ Since $I$ is a PID, we know $(\pi,B)$ has a generator $g$ and you claim (well, not claim-- know) that $gcd(\pi,B)=g$.

So we want a $g$ such that $\{gr: r\in{R}\}=\{\pi{x}+B{y} : x,y\in{R}\}$.

Additionally, $g|\pi$ and $g|B$ implies $gt=\pi$ and $gk=B$ for some $t,k\in{R}$.
This means $g$ is a unit. Because assume it wasn't, then since $\pi$ is irreducible, $t$ must be a unit.
So $\pi{k}=gtk=gkt=Bt$ but that means $\pi{kt^{-1}}=B$ which is a contradiction since we were given $\pi\not{|}B$.

So $g$ is a unit.

Now how can we use the fact that $g$ is a unit, coupled with the fact that $\{gr: r\in{R}\}=\{\pi{x}+B{y} : x,y\in{R}\}$ to show that $g=1$?

Edit: It means for any element $\pi{x_{o}}+B{y_{o}}$ in $\{\pi{x}+B{y} : x,y\in{R}\}$, we have an $r_{o}\in{R}$ such that $gr_{o}=\pi{x_{o}}+B{y_{o}}$. But this means for any $r_{o}\in{R}$, we have $r_{o}=g^{-1}(\pi{x_{o}}+B{y_{o}})$ which implies $g^{-1}$ divides every element in $R$ which means $g$ divides every element in $R$.

But the only thing that divides every element in $R$ is $1$.

Is this correct? :)

 

[Dick]

The ideal $(\pi,B)=\{\pi{x}+By : x,y\in{R}\}$ Since $I$ is a PID, we know $(\pi,B)$ has a generator $g$ and you claim (well, not claim-- know) that $gcd(\pi,B)=g$.

So we want a $g$ such that $\{gr: r\in{R}\}=\{\pi{x}+B{y} : x,y\in{R}\}$.

Additionally, $g|\pi$ and $g|B$ implies $gt=\pi$ and $gk=B$ for some $t,k\in{R}$.
This means $g$ is a unit. Because assume it wasn't, then since $\pi$ is irreducible, $t$ must be a unit.
So $\pi{k}=gtk=gkt=Bt$ but that means $\pi{kt^{-1}}=B$ which is a contradiction since we were given $\pi\not{|}B$.

So $g$ is a unit.

Now how can we use the fact that $g$ is a unit, coupled with the fact that $\{gr: r\in{R}\}=\{\pi{x}+B{y} : x,y\in{R}\}$ to show that $g=1$?

You are going off track here. $1\cdot(\pi{x}+By)=\pi{x}+By$ does not prove that 1 is in the ideal. If that were true then ALL ideals would contain 1. What can you conclude from the fact that $\pi$ is in the ideal and it's irreducible?

 

[robertjordan]

You are going off track here. $1\cdot(\pi{x}+By)=\pi{x}+By$ does not prove that 1 is in the ideal. If that were true then ALL ideals would contain 1. What can you conclude from the fact that $\pi$ is in the ideal and it's irreducible?

Sorry, I rewrote my post going a different direction. What do you think of it now?

 

[Dick]

The ideal $(\pi,B)=\{\pi{x}+By : x,y\in{R}\}$ Since $I$ is a PID, we know $(\pi,B)$ has a generator $g$ and you claim (well, not claim-- know) that $gcd(\pi,B)=g$.

So we want a $g$ such that $\{gr: r\in{R}\}=\{\pi{x}+B{y} : x,y\in{R}\}$.

Additionally, $g|\pi$ and $g|B$ implies $gt=\pi$ and $gk=B$ for some $t,k\in{R}$.
This means $g$ is a unit. Because assume it wasn't, then since $\pi$ is irreducible, $t$ must be a unit.
So $\pi{k}=gtk=gkt=Bt$ but that means $\pi{kt^{-1}}=B$ which is a contradiction since we were given $\pi\not{|}B$.

So $g$ is a unit.

Now how can we use the fact that $g$ is a unit, coupled with the fact that $\{gr: r\in{R}\}=\{\pi{x}+B{y} : x,y\in{R}\}$ to show that $g=1$?




Edit: It means for any element $\pi{x_{o}}+B{y_{o}}$ in $\{\pi{x}+B{y} : x,y\in{R}\}$, we have an $r_{o}\in{R}$ such that $gr_{o}=\pi{x_{o}}+B{y_{o}}$. But this means for any $r_{o}\in{R}$, we have $r_{o}=g^{-1}(\pi{x_{o}}+B{y_{o}})$ which implies $g^{-1}$ divides every element in $R$ which means $g$ divides every element in $R$.

But the only thing that divides every element in $R$ is $1$.




Is this correct? :)

Ah, I see you've changed things. That looks good. You shouldn't be so worried about 1. If an ideal is generated by a unit, then it's the same as the ideal generated by 1, isn't it? In either case it's all of R.

 

[robertjordan]

Ah, I see you've changed things. That looks good. You shouldn't be so worried about 1. If an ideal is generated by a unit, then it's the same as the ideal generated by 1, isn't it? In either case it's all of R.

But how do I say $1$ is the greatest common divisor then if $1$ and any unit $u$ generate the same ideal? How can I say $1$ is greater than $u$?

Also, why do I even need the fact that if $gcd(\pi,B)=g$, then $g$ is the generator of $(\pi,B)$? Is it not enough just to show why any common divisor of $\pi$ and $B$ must be a unit and then explain that $1$ is in some sense the "greatest" of the units (I don't even know if that's true but it relates to my question of how if all units divide $\pi$ and $B$ do we say 1 is the GCD?

Thanks

 

[Dick]

But how do I say $1$ is the greatest common divisor then if $1$ and any unit $u$ generate the same ideal? How can I say $1$ is greater than $u$?

Also, why do I even need the fact that if $gcd(\pi,B)=g$, then $g$ is the generator of $(\pi,B)$? Is it not enough just to show why any common divisor of $\pi$ and $B$ must be a unit and then explain that $1$ is in some sense the "greatest" of the units (I don't even know if that's true but it relates to my question of how if all units divide $\pi$ and $B$ do we say 1 is the GCD?

Thanks

You just have a PID, you don't necessarily have an 'order' to talk about, like in the integers. Are you getting all of your definitions from different places? Looking at the last paragraph of http://en.wikipedia.org/wiki/Greatest_common_divisor notice it refers to d as 'a greatest common divisor', not 'the greatest common divisor'. A gcd is DEFINED as a generator of the ideal. A gcd is generally only unique up to multiplication by a unit.

 

[Dick]

I notice the article also include another definition of gcd you might like better.

"If R is a commutative ring, and a and b are in R, then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = a and d·y = b). If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b."

Can you prove that's equivalent to the ideal statement in a PID? And I think a better phrasing of the definition of relatively prime would be f and g are relatively prime if 1 is A gcd of f and g.

 

[robertjordan]

I notice the article also include another definition of gcd you might like better.

"If R is a commutative ring, and a and b are in R, then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = a and d·y = b). If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b."

Can you prove that's equivalent to the ideal statement in a PID? And I think a better phrasing of the definition of relatively prime would be f and g are relatively prime if 1 is A gcd of f and g.

I'm assuming "the ideal statement" means "If $\{\pi{x}+B{y}: x,y\in{R}\}=\{gr : r\in{R}\}$ then $gcd(\pi,B)=g$.

This is equivalent to "If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b."

Because if $k$ is some arbitrary common divisor of $\pi$ and $B$ then we can rewrite $\{\pi{x}+B{y}: x,y\in{R}\}$ as $\{(kq){x}+(kp){y}: x,y\in{R}\}$ where $k,p\in{R}$. Which is equal to $\{k(q{x}+p{y}): x,y\in{R}\}$ So if $\{gr : r\in{R}\}=\{\pi{x}+B{y}: x,y\in{R}\}$ then $\{gr : r\in{R}\}=\{k(q{x}+p{y}): x,y\in{R}\}$ which means $g\cdot{1}=k(q{x'}+p{y'})$ for some $x',y'\in{R}$, but that means $k|g$.
Is this what you meant?

EDIT: I still don't see why we need all the generator/ linear combinations of $\pi$ and $B$/ ideals stuff...

You said about an element d is a gcd(a,b) in a PID if d|a, d|b and for all other common divisors x of a and b we have x|d.

In post 9 I showed every common divisor of $\pi$ and $B$ is a unit. So that means every common divisor of $\pi$ and $B$ divides 1. And 1 is a common divisor of $\pi$ and $B$ obviously so why is the not enough to say 1 is a $gcd(\pi,B)$?

 

[Dick]

I'm assuming "the ideal statement" means "If $\{\pi{x}+B{y}: x,y\in{R}\}=\{gr : r\in{R}\}$ then $gcd(\pi,B)=g$.

This is equivalent to "If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b."

Because if $k$ is some arbitrary common divisor of $\pi$ and $B$ then we can rewrite $\{\pi{x}+B{y}: x,y\in{R}\}$ as $\{(kq){x}+(kp){y}: x,y\in{R}\}$ where $k,p\in{R}$. Which is equal to $\{k(q{x}+p{y}): x,y\in{R}\}$ So if $\{gr : r\in{R}\}=\{\pi{x}+B{y}: x,y\in{R}\}$ then $\{gr : r\in{R}\}=\{k(q{x}+p{y}): x,y\in{R}\}$ which means $g\cdot{1}=k(q{x'}+p{y'})$ for some $x',y'\in{R}$, but that means $k|g$.



Is this what you meant?

Yeah, that sounds right. A generator of the ideal is divisible by all the common factors.

EDIT: I still don't see why we need all the generator/ linear combinations of $\pi$ and $B$/ ideals stuff...

You said about an element d is a gcd(a,b) in a PID if d|a, d|b and for all other common divisors x of a and b we have x|d.

In post 9 I showed every common divisor of $\pi$ and $B$ is a unit. So that means every common divisor of $\pi$ and $B$ divides 1. And 1 is a common divisor of $\pi$ and $B$ obviously so why is the not enough to say 1 is a $gcd(\pi,B)$?

I'm not sure why you think you can get rid of the ideals stuff. Isn't that how you proved that a gcd was a unit?