Techniques of Solving Equations à la Galois
Profile
Name: scruta \(\quad\)
Daily life: mowing
Revision history
1st upload: 2023/06/17
revision2 : 2023/07/27
revision3 : 2024/12/22
revision4 : 2025/09/14
Contact
Copyright © 2023 scruta
[5-5] The GCD of \(\{H_i\}\) and \(f(x+v)\)
We now finally explain Step 4 of the Trager Algorithm.In the description of the algorithm, thanks to the conclusion at the end of the previous section, we may replace \(\{R_i(x)\}\) by \(\{H_j\}\).
Thus Step 4 of the Trager Algorithm becomes the procedure “compute the GCD (greatest common divisor) of \(\{H_j\}\) and \(f(x+v)\).” As shown in (5.3), that simply means “extract the common factors shared by the two expressions.” As you will immediately see, the common factors are found quite easily.
In (5.4) we have replaced \(v_1\) in (5.1) by \(v\). (A slight cheat.) But since the primitive element was originally \(v=v_1\), this change of notation is acceptable.
\begin{align} &Res( \ f(x + v), \ g(v), \ v)=(-1) \cdot H_1 \cdot H_2 \cdot H_3 \notag \\ &\qquad \left\{ \begin{array}{l} \bbox[#FFFF00]{ H_1=(x+v_1-\alpha)(x+v_4-\beta)(x+v_5-\gamma)} \\ \bbox[#7FFF00]{ H_2=(x+v_1-\beta)(x+v_4-\gamma)(x+v_5-\alpha)} \\ \bbox[#00FFFF]{ H_3=(x+v_1-\gamma)(x+v_4-\alpha)(x+v_5-\beta)} \\ \end{array} \right. \\ \notag \\ &f(x+v_1)=Y_1 \cdot Y_2 \cdot Y_3 \qquad \left\{ \begin{array}{l} \bbox[#FFFF00]{Y_1=(x+v_1-\alpha)} \\ \bbox[#7FFF00]{Y_2=(x+v_1-\beta)} \\ \bbox[#00FFFF]{Y_3=(x+v_1-\gamma)} \\ \end{array} \right. \\ \end{align}
\begin{align} &\qquad \Downarrow \notag \\ &\left\{ \begin{array}{l} GCD\bigl( \bbox[#FFFF00]{H_1},f(x+v_1)\bigr)= GCD\bigl( \bbox[#FFFF00]{H_1},\bbox[#FFFF00]{Y_1} \cdot \bbox[#7FFF00]{Y_2} \cdot \bbox[#00FFFF]{Y_3}\bigr)= \bbox[#FFFF00]{Y_1}=\bbox[#FFFF00]{(x+v_1-\alpha)} \\ GCD\bigl( \bbox[#7FFF00]{H_2},f(x+v_1)\bigr)= GCD\bigl( \bbox[#7FFF00]{H_2},\bbox[#FFFF00]{Y_1} \cdot \bbox[#7FFF00]{Y_2} \cdot \bbox[#00FFFF]{Y_3}\bigr) = \bbox[#7FFF00]{Y_2} =\bbox[#7FFF00]{(x+v_1-\beta)} \\ GCD\bigl( \bbox[#00FFFF]{H_3},f(x+v_1)\bigr)=GCD\bigl( \bbox[#00FFFF]{H_3},\bbox[#FFFF00]{Y_1} \cdot \bbox[#7FFF00]{Y_2} \cdot \bbox[#00FFFF]{Y_3}\bigr)=\bbox[#00FFFF]{Y_3}= \bbox[#00FFFF]{(x+v_1-\gamma)} \\ \end{array} \right. \\ &\qquad \Downarrow \notag \\ &\left\{ \begin{array}{l} GCD\bigl(\left. \bbox[#FFFF00]{H_1} \right|_{v_1=v} \ ,f(x+v)\bigr)= \bbox[#FFFF00]{(x+v-\alpha)}=\left. Y_1 \right|_{v_1=v} \\ GCD\bigl(\left. \bbox[#7FFF00]{H_2} \right|_{v_1=v} \ ,f(x+v)\bigr)= \bbox[#7FFF00]{(x+v-\beta)}=\left. Y_2 \right|_{v_1=v} \\ GCD\bigl(\left. \bbox[#00FFFF]{H_3} \right|_{v_1=v} \ ,f(x+v)\bigr)= \bbox[#00FFFF]{(x+v+\gamma)}=\left. Y_3 \right|_{v_1=v} \\ \end{array} \right. \\ \end{align}
Equation (5.6) is the final target, but it is merely a rewrite of (5.4) with a slight leap. At the stage where we compute the resultant, we do not yet know the roots of \(f(x)\), so we cannot make such identifications, and thus we cannot determine \(\{H_i\}\) as defined in (5.1).
However, the conclusion of [5-4] guarantees that “even if the roots of \(f(x)\) are unknown, the resultant \(Res(f(x+v),g(v),v)\) factors as a product of polynomials.”
Therefore, regardless of order, the result of computing the resultant should yield polynomials \(\{R(x)_i\}\) corresponding to \(\{H_i\}\). Furthermore, by computing the GCDs of \(\{R(x)_i\}\) with \(f(x+v)\), we should obtain expressions \(\{\tilde{Y}_j(x)\}\) corresponding to the \(Y_i\), again up to order. This is what (5.5) and (5.6) express.
Since we cannot match each \(R_i(x)\) with a specific root, (5.6) expresses the roots of \(f(x)\) using symbols \(x_i\). Finally, using these \(\{\tilde{Y}_j(x)\}\), we can factor \(f(x)\) as in (5.7).
\begin{align} &\{H_1,H_2,H_3\} \ \rightarrow \ \{R_1(x),R_2(x),R_3(x)\}, \quad \{Y_1,Y_2,Y_3\} \ \rightarrow \ \{\tilde{Y}_1(x),\tilde{Y}_2(x),\tilde{Y}_3(x)\} \\ &\qquad \Downarrow \notag \\ \end{align}
\begin{align} &\left\{ \begin{array}{l} GCD\bigl(R_1(x),f(x+v)\bigr)=(x+v-x_1) \equiv \tilde{Y}_1(x) \\ GCD\bigl(R_2(x),f(x+v)\bigr)=(x+v-x_2) \equiv \tilde{Y}_2(x) \\ GCD\bigl(R_3(x),f(x+v)\bigr)=(x+v-x_3) \equiv \tilde{Y}_3(x) \\ \end{array} \right. \\ \notag \\ &\therefore \ f(x)=\tilde{Y}_1(x-v) \cdot \tilde{Y}_2(x-v) \cdot \tilde{Y}_3(x-v)=(x-x_1)(x-x_2)(x-x_3) \\ \end{align}
[5-6] Computing the GCDs of \(\{R_i(x)\}\) and \(f(x+v)\)
We now actually compute the greatest common divisors of \(\{R_i(x)\}\) and \(f(x+v)\) using the Euclidean algorithm.Note that the Euclidean algorithm is carried out with respect to the variable \(x\). The computations are performed over the algebraic number field \(F_0(v)\) generated by \(g(v)\). For readability of the intermediate expressions, we display each step in matrix form. To keep the computations from getting unwieldy, we extract the leading coefficient of each remainder polynomial as \(c_i\) so that the leading coefficient of each \(r_i\) becomes \(1\). At the same time we also compute the reciprocals \(c_i^{-1}\).
\begin{align} &(step.6-0) \notag \\ \notag \\ &r_0=R_1={{x}^{3}}-21 x+17 \\ &r_1=f(x+v)=(x+v)^3-3(x+v)-1={{x}^{3}}+3 v {{x}^{2}}+3 {{v}^{2}} x-3 x+{{v}^{3}}-3 v-1 \notag \\ &\qquad \qquad \qquad ={{x}^{3}}+3 v {{x}^{2}}+3 {{v}^{2}} x-3 x+6 v+10 \quad ( \ mod \ g(v) \ )\\ \notag \\ &(step.6-1) \ Euclidean Algorithm \notag \\ \notag \\ &\begin{pmatrix} r_0\\r_1 \end{pmatrix} = \begin{pmatrix} q_1 & c_2 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_1\\r_2 \end{pmatrix} \qquad Q_1= \begin{pmatrix} q_1 & c_2 \\ 1 & 0 \end{pmatrix} \qquad Q_1^{-1}=\frac{1}{c_2}\cdot \begin{pmatrix} 0 & c_2 \\ 1 & -q_1 \end{pmatrix} \\ \notag \\ &q_1=1 \qquad r_2={{x}^{2}}+\frac{2 {{v}^{2}} x}{3}+v x-6 x-{{v}^{2}}+11 \\ &c_2=-3v \qquad \frac{1}{c_2}=c_2^{-1}=\frac{1}{3}-\frac{{{v}^{2}}}{27} \qquad c_2\cdot c_2^{-1}=1 \quad ( \ mod \ g(v) \ ) \notag \\ \notag \\ &(step.6-2) \ Euclidean Algorithm \notag \\ \notag \\ &\begin{pmatrix} r_1\\r_2 \end{pmatrix} = \begin{pmatrix} q_2 & c_3 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_2\\r_3 \end{pmatrix} \qquad Q_2= \begin{pmatrix} q_2 & c_3 \\ 1 & 0 \end{pmatrix} \qquad Q_2^{-1}=\frac{1}{c_3} \cdot \begin{pmatrix} 0 & c_3 \\ 1 & -q_2 \end{pmatrix} \\ \notag \\ &q_2=x-\frac{2 {{v}^{2}}}{3}+2 v+6 \qquad \bbox[#FFFF00]{r_3=x+\frac{{{v}^{2}}}{3}+v-2} \\ &c_3=-2 {{v}^{2}}+4 v+16 \qquad \frac{1}{c_3}=c_3^{-1}=-\frac{3 {{v}^{2}}}{38}+\frac{7 v}{38}+\frac{17}{38} \qquad c_3\cdot c_3^{-1}=1 \quad ( \ mod \ g(v) \ ) \notag \\ \notag \\ &(step.6-3) \ Euclidean Algorithm \notag \\ \notag \\ &\begin{pmatrix} r_2\\r_3 \end{pmatrix} = \begin{pmatrix} q_3 & c_4 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_3\\r_4 \end{pmatrix} \qquad Q_3= \begin{pmatrix} q_3 & c_4 \\ 1 & 0 \end{pmatrix} \qquad Q_3^{-1}=\frac{1}{c_4} \cdot \begin{pmatrix} 0 & c_4 \\ 1 & -q_3 \end{pmatrix} \\ \notag \\ &q_3=x+\frac{{{v}^{2}}}{3}-4 \qquad r_4=0 \\ &c_4=1 \qquad \frac{1}{c_4}=c_4^{-1}=1 \qquad c_4\cdot c_4^{-1}=1 \quad ( \ mod \ g(v) \ ) \notag \\ \end{align}
\begin{align} &\left\{ \begin{array}{l} \tilde{Y}_1(x) \equiv x+v-x_1=GCD(R_1(x),f(x+v))=x+\frac{{{v}^{2}}}{3}+v-2\\ \tilde{Y}_2(x) \equiv x+v-x_2=GCD(R_2(x),f(x+v))= x-\frac{2 {{v}^{2}}}{3}+2 v+4 \\ \tilde{Y}_3(x) \equiv x+v-x_3=GCD(R_3(x),f(x+v))=x+\frac{{{v}^{2}}}{3}-2 \\ \end{array} \right. \\ \end{align}
\begin{align} &f(x)=\tilde{Y}_1(x-s \cdot v) \cdot \tilde{Y}_2(x-s \cdot v) \cdot \tilde{Y}_3(x-s \cdot v)=(x-x_1)(x-x_2)(x-x_3) \\ \notag \\ &\biggl[ x_1=-\frac{{{v}^{2}}}{3}+2 , \quad x_2=\frac{2 {{v}^{2}}}{3}-v-4, \quad x_3=-\frac{{{v}^{2}}}{3}+v+2 \ \biggr] \\ \end{align}
The three roots \(\{x_1,x_2,x_3\}\) in (6.10) match those in (3.4) of Chapter 4 (up to ordering).
The above completes the procedure and rationale for factoring \(f(x)\) over the algebraic number field \(F_0(v)\) using the Trager Algorithm.