0
$\begingroup$

I need some help with the following division proofs. I suppose my biggest problem is not being able to visualize the algebra for one GCD equaling another GCD. I'm not sure of how to arrange the variables.

Let $F$ be a field and $f,g,q,r \in F[X]$ with $f$ being nonzero and $g=fq+r$

A. Prove that $d$ is a greatest common divisor of $f$ and $g$ if and only if $d$ is a greatest common divisor of $f$ and $r$.

B. Prove that the last nonzero remainder of Euclid’s Algorithm on $f$ and $g$ is a greatest common divisor of $f$ and $g$.

C. Show that there are polynomials $r,t \in F[X]$ such that $d = rf +tg$

$\endgroup$
1
$\begingroup$

A greatest common divisor of $f$ and $g$ is a polynomial $d$ such that

  1. $d$ divides both $f$ and $g$;
  2. if $e$ is a polynomial that divides both $f$ and $g$, then $e$ divides $d$.

(A) Suppose $d$ is a greatest common divisor of $f$ and $g$; then by (1), we can write $f=df_1$ and $g=dg_1$; therefore $$ r=fq-g=d(f_1q-g_1) $$ and so $d$ satisfies property (1) with respect to $g$ and $q$. Next, suppose $e$ divides both $g$ and $r$: $g=eg_2$, $r=er_2$; then $f=gq+r=e(g_2q+r_2)$, which means that $e$ divides both $f$ and $g$, so by (2) we conclude that $e$ divides $d$. Hence $d$ satisfies also property (2) with respect to $g$ and $r$.

The converse direction is very similar.

(B) At each step of the Euclidean algorithm the greatest common divisor is preserved because of (A). The last step gives a zero remainder, so the divisor is obviously a greatest common divisor of itself and the dividend. But this divisor is exactly the last nonzero remainder.

(C) Traverse the steps in the algorithm.

$\endgroup$
0
$\begingroup$

For part $(A)$, suppose that $d$ is a gcd of $f$ and $g$ and $d'$ is a gcd of $f$ and $r$. Then $d\mid (g-fq)=r$ because $d\mid g$ and $d\mid f$, so $d\mid d'$ (because $d'$ is a greatest common divisor of $r$ and $f$.) Similarly, $d'\mid (fq+r)=g$ and $d'\mid f$, so $d'\mid d$. Hence, $d'$ and $d$ differ by at most multiplication by a constant polynomial, and so each is a gcd of $g$ and $f$ and $f$ and $r$.

Parts $(B)$ and $(C)$ follow from $(A)$ simply by applying the Euclidean algorithm.

For $(B)$, you just apply $(A)$ at each step of the Euclidean algorithm to get that the last nonzero remainder is also a gcd of $f$ and $g$.

For $(C)$, starting at the last equation you get in the Euclidean algorithm (which will be of the form $g_k=q_kf_k+d$ for some $g_k$, $q_k$, and $f_k$,) take the equation $d=g_k-q_kf_k$ and back-substitute for $g_k$ and $f_k$ with the earlier equations in the Euclidean algorithm to get an equation of the desired form for $(C)$.

Here is an example using the Euclidean algorithm in $\mathbb{Z}$ to demonstrate this: \begin{align*} 5 &= 1\cdot 3+2 \\ 3 &= 1\cdot 2+1, \end{align*} so take $1=3-1\cdot 2$, substitute in $2=5-1\cdot 3$ from the previous equation, and you get $1=3-1\cdot(5-1\cdot 3)=2\cdot 3-1\cdot 5$.

$\endgroup$
0
$\begingroup$

Let's $\mathbb{F}=F[X]$ and $Id(f,g)=\mathbb{F}f + \mathbb{F}g$ the ideal generated by $f$ and $g$. I don't know if you know the definition of the gcd with ideals, so I did proofs with and proof without.

A. "Ideals" : We suppose $f \neq 0$. Since $r=g-fq$, it is clear that $Id(f,r)=\mathbb{F}f + \mathbb{F}r = \mathbb{F}f + \mathbb{F}(g - fq) \subset Id(f,g)$ since its element are linear combination of $f$ and $g$. So $gcd(f,g) \mid gcd(f,r)$. Conversly, $sf + tg \in Id(f,g)$ can be written as $(s-tq+tq)f + tg=s'f - tqf + tg=s'f + t(g - qf)=s'f + tr \in Id(f,r)$ where $s'=s+tq$. So, finally $Id(f,g)=Id(f,r)$ and $gcd(f,g)=gcd(f,r)$.

"Usual" : It is known (and trivial to show) that if $d \mid f,g$ then $d$ divide any linear combination of $f$ and $g$ (I say linear but the coeffecient can be in $\mathbb{F}$), and especially $d \mid r = g -qf$ and so $d \mid f,r$. Conversely, if $d \mid r,f$ then $d \mid g=fq + r$ and finally $\{$ Common divisors of $f$ and $g \} = \{$ Common divisor of $f$ and $r \}$ and it follows that $gcd(f,g)=gcd(f,r)$

B. You can use the usual proof (http://en.wikipedia.org/wiki/Euclidean_algorithm#Proof_of_validity), using the A. lemma instead of the usual one on integers, and it works well.

C. With the definition on ideals, there is nothing to prove, since $gcd(f,g) \in Id(f,g)$.

"Usual" : this is also the same proof than for integers, using Bezout's theorem (which is still valid for polynomials) or Euclide algorithm (that provides with the actual coefficients).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.