# Euclid's Lemma for polynomials

I need your help with this: Let $f$, $p$, and $g$ be a polynomials in $F[x]$, assume that $f$, $g$, and $p$ are nononzero.

If $\gcd(f,p)=1$ and $fg$ is divisible by $p$ with no remainder, I need to prove that $g$ is divisible by $p$ with no remainder

Thanks.

-

Polynomials over a field are an Euclidean domain relative to the degree function. In particular, for every polynomials $a(x)$ and $b(x)$ in $F[x]$, with $b(x)\neq 0$, there exist unique polynomials $q(x),r(x)\in F[x]$ such that $$a(x) = q(x)b(x) + r(x),\quad\mbox{r(x)=0 or \mathrm{deg}(r)\lt \mathrm{deg}(b)}$$

So the Euclidean algorithm also applies to polynomials. In particular, if $q(x) = \gcd(m(x),n(x))$, then there exist polynomial $\alpha(x),\beta(x)$ such that $q(x) = \alpha(x)m(x) + \beta(x)n(x)$.

Now you can use the same proof as the proof of Euclid's Lemma for integers: if $a|bc$ and $\gcd(a,b)=1$, then $a|c$.

-
Arturo, I understand the defenitions that you wrote, but How does the information relates to Euclid's Lemma? can I use just the Lemma? –  user6163 Mar 14 '11 at 20:56
@Nir: Not directly, because the Lemma is for integers. But the proof is the same. Find any proof of Euclid's lemma that uses Bezout's identity for the gcd. If you understand that proof, you will be able to make the trivial changes necessary to get a proof for the polynomials. The point is that the essence of the proof is not about integers or polynomials, but about the fact that you can write the gcd as a linear combination. Bill's proof works in the even more general setting of gcd domains. –  Arturo Magidin Mar 14 '11 at 20:58
Thnaks Arturo. I want to know If I got the whole gcd and polynomials concept. if gcd(f,g)=1, It means that there are polynomials a and b so that 1=ag+fb? and if I know that gcd(f,p) is also 1, can I write that there are a,b,c,d so that ag+bf=cf+dp? –  user6163 Mar 14 '11 at 21:31
@Nir: No. In this problem, you do not know that $\gcd(f,g)=1$; there is absolute no warrant for making that asusmption. What you know is that $\gcd(f,p)=1$. That means there are polynomials $a$ and $b$ such that $1=af+bp$. You also know that $p$ divides $fg$. Now, if $1=af+bp$, then what is $g$? (Hint: $g$ is the same thing as $g$ multiplied by $1$). Use that to show that $g$ is a multiple of $p$. –  Arturo Magidin Mar 15 '11 at 2:42
@Nir: The proof in en.wikipedia.org/wiki/… is directly applicable. –  Arturo Magidin Mar 15 '11 at 3:04

Proof $\rm\ \ \ p\ |\ fg,\:pg\ \Rightarrow\ p\ |\ (fg,pg)\ =\ (f,p)\ g\ =\ g\$ since $\rm\ (f,p)\ =\ 1\:.\quad\$ QED

This proof of Euclid's Lemma works in any GCD domain, e.g. any domain like $\rm\:F[x]\:$ enjoying a Euclidean algorithm to compute the GCD.

-
Thank you for the comment bill. (fg,pg) is a short expression for gcd(fg,pg)? and if it is, why does p divide the gcd of (fp,pg)? thanks. –  user6163 Mar 14 '11 at 20:38
@Nir: Because it divides both $fp$ and $pg$. By definition of the gcd, it is a common divisor, and it is a multiple of all common divisors (hence "greatest", in the partial order induced by divisibility). In short, "by definition." –  Arturo Magidin Mar 14 '11 at 20:42
Thank you Arturo. –  user6163 Mar 14 '11 at 20:47
@Nir: One useful and general way to define the gcd is $\rm\ \ c\ |\ a,b\ \iff\ c\ |\ (a,b)\:.\$ Note that for $\rm\ c = (a,b)\$ the $\:(\Leftarrow)\:$ shows that $\rm\:(a,b)\:$ is a common divisor of $\rm\:a,b\:,\:$ and $\:(\Rightarrow)\:$ shows that it is divisible by every common divisor $\rm\:c\:.\$ Therefore this definition is equivalent to the more common definition of the greatest common divisor. But this definition is more useful in proofs since it allows one to prove both implication directions simultaneously. –  Bill Dubuque Mar 15 '11 at 16:26

If $gcd(f, p) = 1$ then $af + bp = 1$ for some $a, b \in \Bbb{Z}$. But multiplying by $g$ on each side, $g = gaf + gbp$ and therefore $g = a(fg) + bg(p)$.

Let $fg = cp$ for some $c \in \Bbb{Z}$. Then $g = p(ac + bg)$ implying $p|g$. QED.

-