1
$\begingroup$

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.

3 Answers 3

0

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.

2

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.

  • 0
    @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.2011-03-15
1

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$.

  • 0
    @Nir: The proof in http://en.wikipedia.org/wiki/Euclid%27s_lemma#Proof_of_Euclid.27s_lemma is directly applicable.2011-03-15