19th Ave New York, NY 95822, USA

# 数学代写|现代代数代考Modern Algebra代写|MA320

my-assignmentexpert™提供最专业的一站式服务：Essay代写，Dissertation代写，Assignment代写，Paper代写，Proposal代写，Proposal代写，Literature Review代写，Online Course，Exam代考等等。my-assignmentexpert™专注为留学生提供Essay代写服务，拥有各个专业的博硕教师团队帮您代写，免费修改及辅导，保证成果完成的效率和质量。同时有多家检测平台帐号，包括Turnitin高级账户，检测论文不会留痕，写好后检测修改，放心可靠，经得起任何考验！

## 数学代写|现代代数代考Modern Algebra代写|The resultant

The central goal of this whole chapter is to find modular ged algorithms for domains like $\mathbb{Z}[x], \mathbb{Q}[x]$, and $F[x, y]$. Section 6.13 reports on implementations that show how much these algorithms are superior to the “traditional” one, whose problems are quite visible in Example 6.1. The simplest such approach, the big prime modular algorithm, chooses a large prime $p$, calculates the gcd modulo $p$, and recovers the true gcd from its modular image. This is quite easy, provided that the modular gcd is indeed the image of the true gcd; this may, in fact, fail in exceptional cases.

This section provides a general tool, the resultant, to control modular images of the gcd. This introduces linear algebra into our polynomial problems. We also discuss other applications, such as curve intersection and minimal polynomials of algebraic elements. In Section 6.10, we introduce the subresultants, a generalization that gives us control over all results of the EEA. But the reader should realize clearly that for gcd calculations the resultant is purely an (indispensable) conceptual tool and does not enter the algorithms, but only their analysis.

Now let $F$ be a field and $f, g \in F[x]$. The following lemma says that the vanishing linear combination $(-g) \cdot f+f \cdot g=0$ has the smallest possible coefficient degrees if and only if $\operatorname{gcd}(f, g)=1$.

Lemma 6.13. Let $f, g \in F[x]$ be nonzero. Then $\operatorname{gcd}(f, g) \neq 1$ if and only if there exist $s, t \in F[x] \backslash{0}$ such that $s f+t g=0, \operatorname{deg} s<\operatorname{deg} g$, and $\operatorname{deg} t<\operatorname{deg} f$.

Proof. Let $h=\operatorname{gcd}(f, g)$. If $h \neq 1$, then $\operatorname{deg} h \geq 1$, and $s=-g / h, t=f / h$ suffice. Conversely, let $s, t$ be as assumed. If $f$ and $g$ were coprime, then $s f=-t g$ would imply that $f \mid t$, which is impossible since $t \neq 0$ and $\operatorname{deg} f>\operatorname{deg} t$. This contradiction shows that $h \neq 1$.

## 数学代写|现代代数代考Modern Algebra代写|Modular gcd algorithms

Our goal in this and the following sections is to provide a modular gcd algorithm for $\mathbb{Z}[x]$ and $F[x, y]$. We start by investigating the relation between the modular image of the gcd and the gcd of modular images. It turns out that they are usually (essentially) equal, but this fails for the “unlucky primes” that divide a certain resultant.

We let $f, g \in R[x]$ for a Euclidean domain $R, p \in R$ a prime, and denote by a bar the reduction modulo $p$. Corollary 6.20 says that $\operatorname{gcd}(f, g)$ is constant if and only if $\operatorname{res}(f, g) \neq 0$. The resultant $\operatorname{res}(f, g) \in R$ is a polynomial expression in the coefficients of $f$ and $g$, and one might be tempted to say: since $\overline{\operatorname{res}(f, g)}=$ $\operatorname{res}(\bar{f}, \bar{g}), \bar{f}$ and $\bar{g}$ are coprime in $(R /\langle p\rangle)[x]$ if and only if $p \nmid \operatorname{res}(f, g)$.

EXAMPLE 6.24. To get a taste of what can go wrong without further assumptions, we let $R=\mathbb{Z}$ and $p=2$. When $f=x+2$ and $g=x$, then $\operatorname{res}(f, g)=-2 \neq 0$ and $\operatorname{res}(\bar{f}, \bar{g})=0$, as expected. But when $f=4 x^3-x$ and $g=2 x+1$, then $\operatorname{res}(f, g)=0$ and $\operatorname{res}(\bar{f}, \bar{g})=\operatorname{res}(x, 1)=1 \neq 0$; in particular, $\overline{\operatorname{res}(f, g)} \neq \operatorname{res}(\bar{f}, \bar{g})$.

The reason for the unexpected behavior in the last example is that the two relevant Sylvester matrices are formed in rather different ways. Fortunately, this nuisance disappears when $p$ does not divide at least one of the leading coefficients.
Lemma 6.25. We let $R$ be a ring (commutative, with 1 ), $f, g \in R[x]$ nonzero, $r=\operatorname{res}(f, g) \in R, I \subseteq R$ an ideal, denote by a bar the reduction modulo $I$, and assume that $\overline{\operatorname{lc}(f)}$ is not a zero divisor.
(i) $\bar{r}=0 \Longleftrightarrow \operatorname{res}(\bar{f}, \bar{g})=0$.
(ii) If $R / I$ is a UFD, then $\bar{r}=0$ if and only if $\operatorname{gcd}(\bar{f}, \bar{g})$ is nonconstant.

# 现代代数代写

## 数学代写|现代代数代考Modern Algebra代写|Modular gcd algorithms

(i) $\bar{r}=0 \Longleftrightarrow \operatorname{res}(\bar{f}, \bar{g})=0$。
(ii)如果$R / I$是UFD，则当且仅当$\operatorname{gcd}(\bar{f}, \bar{g})$是非常量时，则$\bar{r}=0$。