Add Galois lab 1
Change-Id: I888fc143dba834e1d4575d4c5c2ed43a4008d5ba
diff --git a/quad9/galois/labs/lab1/main.tex b/quad9/galois/labs/lab1/main.tex
new file mode 100644
index 0000000..af6f3d6
--- /dev/null
+++ b/quad9/galois/labs/lab1/main.tex
@@ -0,0 +1,274 @@
+\documentclass[11pt,a4paper,dvipsnames]{article}
+\usepackage[utf8]{inputenc}
+
+\usepackage[catalan]{babel}
+\input{../../../hw_preamble.tex}
+
+\title{Laboratori 2: Discriminant\\Teoria de Galois}
+\author{Adrià Vilanova Martínez}
+
+\printversionfalse % "true": print version (no colors), "false": display version
+\showcorrectionsfalse % Change "true" to "false" in order to show corrections as
+ % if they weren't corrections (in black instead of red).
+
+% Ruffini macro (source: https://tex.stackexchange.com/a/122728)
+\usepackage{xparse}
+\ExplSyntaxOn
+\NewDocumentCommand{\ruffini}{mmmm}
+ {% #1 = polynomial, #2 = divisor, #3 = middle row, #4 = result
+ \franklin_ruffini:nnnn { #1 } { #2 } { #3 } { #4 }
+ }
+
+\seq_new:N \l_franklin_temp_seq
+\tl_new:N \l_franklin_scheme_tl
+\int_new:N \l_franklin_degree_int
+
+\cs_new_protected:Npn \franklin_ruffini:nnnn #1 #2 #3 #4
+ {
+ % Start the first row
+ \tl_set:Nn \l_franklin_scheme_tl { #2 & }
+ % Split the list of coefficients
+ \seq_set_split:Nnn \l_franklin_temp_seq { , } { #1 }
+ % Remember the number of columns
+ \int_set:Nn \l_franklin_degree_int { \seq_count:N \l_franklin_temp_seq }
+ % Fill the first row
+ \tl_put_right:Nx \l_franklin_scheme_tl
+ { \seq_use:Nnnn \l_franklin_temp_seq { & } { & } { & } }
+ % End the first row and leave two empty places in the next
+ \tl_put_right:Nn \l_franklin_scheme_tl { \\ & & }
+ % Split the list of coefficients and fill the second row
+ \seq_set_split:Nnn \l_franklin_temp_seq { , } { #3 }
+ \tl_put_right:Nx \l_franklin_scheme_tl
+ { \seq_use:Nnnn \l_franklin_temp_seq { & } { & } { & } }
+ % End the second row
+ \tl_put_right:Nn \l_franklin_scheme_tl { \\ }
+ % Compute the \cline command
+ \tl_put_right:Nx \l_franklin_scheme_tl
+ {
+ \exp_not:N \cline { 2-\int_to_arabic:n { \l_franklin_degree_int + 1 } }
+ }
+ % Leave an empty place in the third row (no rule either)
+ \tl_put_right:Nn \l_franklin_scheme_tl { \multicolumn{1}{r}{} & }
+ % Split and fill the third row
+ \seq_set_split:Nnn \l_franklin_temp_seq { , } { #4 }
+ \tl_put_right:Nx \l_franklin_scheme_tl
+ { \seq_use:Nnnn \l_franklin_temp_seq { & } { & } { & } }
+ % Start the array (with \use:x because the array package
+ % doesn't expand the argument)
+ \use:x
+ {
+ \exp_not:n { \begin{array} } { r | *{\int_use:N \l_franklin_degree_int} { r } }
+ }
+ % Body of the array and finish
+ \tl_use:N \l_franklin_scheme_tl
+ \end{array}
+ }
+\ExplSyntaxOff
+
+\begin{document}
+
+\maketitle
+
+\section{Fórmula de Cardano}
+
+\begin{Problem}
+ Feu un canvi de variable del tipus $X = Y - m$ per transformar l'equació inicial en una equació:
+ \[ Y^3 + pY + q = 0, \quad p, q \in K \]
+
+ \begin{enumerate}[a)]
+ \item Expresseu $p, q$ en termes de $b, c, d$.
+ \item Expresseu les arrels $\beta_1, \beta_2, \beta_3$ de la nova equació en termes d'$\alpha_1, \alpha_2, \alpha_3$.
+ \end{enumerate}
+\end{Problem}
+
+\textbf{Apartat a):} \\
+\[ 0 = a(Y - m)^3 + b(Y - m)^2 + c(Y - m) + d = \]
+\[ = a(Y^3 - 3 Y^2 m + 3 Y m^2 - m^3) + b(Y^2 - 2Ym + m^2) + c(Y - m) + d = \]
+\[ = aY^3 + (-3am + b)Y^2 (3am^2 - 2bm + c)Y + (-am^3 + bm^2 - cm + d). \]
+
+Per no liar molt la troca suposarem des del principi $a = 1$. Podem considerar que el que hem fet és multiplicar l'equació per $a^{-1}$, i treballem sobre les variables $\tilde{b} = ba^{-1}$, $\tilde{c} = ca^{-1}$, $\tilde{d} = da^{-1}$.
+
+Aleshores, igualant coeficients, obtenim:
+\[ \left\{ \begin{array}{l}
+ -3m + b = 0 \implies m = \frac{b}{3}, \\
+ 3m^2 - 2bm + c = p \implies 3 \frac{b^2}{9} - 2b \frac{b}{3} + c = p \implies \frac{b^2}{3} - \frac{2}{3}b^2 + c = p \implies -\frac{b^2}{3} + c = p, \\
+ -m^3 + bm^2 - cm + d = q \implies - \frac{b^3}{27} + \frac{b^3}{9} - c\frac{b}{3} + d = q \implies \frac{2b^3}{27} - \frac{cb}{3} + d = q,
+\end{array} \right\} \implies \]
+\[ \implies \begin{cases}
+ m = \frac{b}{3}, \\
+ p = c - \frac{b^2}{3}, \\
+ q = \frac{2}{27}b^3 - \frac{cb}{3} + d.
+\end{cases} \]
+
+\textbf{Apartat b):} \\
+Si anomenem $P(X) := aX^3 + bX^2 + cX + d$ i $Q(Y) := Y^3 + pY + q = 0$, aleshores:
+\[ Q(Y) = P(Y - m). \]
+Per tant,
+\[ \forall \beta_i : Q(\beta_i) = 0 \implies P(\beta_i - m) 0 0 \implies \beta_i - m = \alpha_i \implies \beta_i = \alpha_i + m. \]
+
+\begin{Problem}
+ Comproveu que el canvi $Y = U - V$ transforma l'equació anterior en:
+ \[ (U^3 - V^3) - (3UV - p)(U - V) + q = 0. \]
+ Feu el canvi $V = p/(3U)$ per obtenir l'equació
+ \[ U^6 + qU^3 - p^3/27 = 0. \]
+\end{Problem}
+
+\[ 0 = (U - V)^3 + p(U - V) + q = U^3 - V^3 + 3UV^2 - 3U^2V + p(U - V) + q = \]
+\[ = (U^3 - V^3) + 3UV(V - U) + p(U - V) + q = \]
+\[ = (U^3 - V^3) + (-3UV + p)(U - V) + q = \]
+\[ = (U^3 - V^3) - (3UV - p)(U - V) + q. \]
+
+Així doncs, fent la substitució $V = \frac{p}{3U}$:
+\[ 0 = \left( U^3 - \frac{p^3}{27 U^3} \right) - \cancel{\left( 3 \frac{p}{3} - p \right)}(U - V) + qU^3 \implies \]
+\[ \implies 0 = U^6 + qU^3 - \frac{p^3}{27}. \]
+
+\begin{Problem}
+ Trobeu els dos valors $z_1, z_2 \in \bar{K}$ de $U^3$ que són solució de l'equació anterior.
+\end{Problem}
+
+Fem el canvi $U^3 = T$. Aleshores:
+\[ T^2 + qT - \frac{p^3}{27} = 0. \]
+
+Apliquem la fórmula de l'equació de segon grau ``a cegues'' (tal com vam comentar a la primera classe): (treballem a $\bar{K}$ on existeixen totes les arrels)
+\[ z_{1, 2} = \frac{-q \pm \sqrt{q^2 + 4 \frac{p^3}{27}}}{2}. \]
+
+\begin{Problem}
+ Trieu una arrel cúbica $u_1 \in \bar{K}$ de $z_1$, i preneu $v_1 = \frac{p}{3 u_1}$. Comproveu que:
+ \[ v_1^3 = - z_2, \quad u_1^3 + v_1^3 = -q. \]
+\end{Problem}
+
+Observem que $v_1^3 = - z_2 \iff \frac{v_1^3}{z_2} = -1$. Per tant, calculem el membre de l'esquerra:
+\[ \frac{v_1^3}{z_2} = \frac{p^3}{3^3 u_1^3 z_2} = \frac{p^3}{27 z_1 z_2}. \]
+
+A més:
+\[ z_1 z_2 = \frac{1}{4} \left( - q + \sqrt{q^2 + 4 \frac{p^3}{27}} \right) \cdot \left( - q - \sqrt{q^2 + 4 \frac{p^3}{27}} \right) = \frac{1}{4} \left( q^2 - q^2 - 4 \frac{p^3}{27} \right) = - \frac{p^3}{27}. \]
+
+Per tant, substituint a l'expressió anterior:
+\[ \frac{v_1^3}{z_2} = \frac{p^3}{27} \cdot \left( - \frac{27}{p^3} \right) = -1. \]
+
+Ara demostrarem $u_1^3 - v_1^3 = -q$:
+\[ u_1^3 = z_1, v_1^3 = \frac{p^3}{27 u_1^3} \implies \]
+\[ \implies u_1^3 - v_1^3 = z_1 - \frac{p^3}{27 z_1} = \frac{27 z_1^2 - p^3}{27 z_1} \implies \]
+\[ \implies z_1(u_1^3 - v_1^3) = z_1^2 - \frac{p^3}{27} \notate[X]{{}={}}{1}{\scriptstyle \text{Eq. } \left. T^2 + qT - \frac{p^3}{27} \right|_{T = z_1} = 0} - qz_1 \implies \]
+\[ \implies u_1^3 - v_1^3 = -q. \]
+
+\begin{Problem}
+ Comproveu que $u_1 - v_1$ és una arrel de l'equació $Y^3 + pY + q = 0$. Quines són les altres arrels? Escriviu fórmules generals per a les arrels $\beta_1, \beta_2, \beta_3$.
+\end{Problem}
+
+Ha de ser arrel pel canvi de variables que hem fet. Anem a comprovar-ho:
+\[ (u_1 - v_1)^3 + p(u_1 - v_1) + q = \underbrace{\cancel{u_1^3 - v_1^3}}_{-q} + 3u_1v_1^2 - 3u_1^2v_1 + p(u_1 - v_1) + \cancel{q} = \]
+\[ = (p - 3u_1v_1)(u_1 - v_1) \notate[X]{{}={}}{1}{v_1 = \frac{p}{3u_1}} \left( p - 3u_1\frac{p}{3u_1} \right)(u_1 - v_1) = (p - p)(u_1 - v_1) = 0. \]
+
+Donat que hem considerat 1 arrel cúbica en concret de $z_1$ i no les altres 2 arrels cúbiques, per construir les altres 2 arrels prenem $u_2, u_3 \in \bar{K}$ arrels cúbiques diferents de $z_1$ (o $z_2$) i prenem $v_i = \frac{p}{3 u_i}$. Aleshores: $u_i - v_i =: \beta_i$ seran les arrels de l'equació $Y^3 + pY + q = 0$.
+
+Això és perquè el procediment amb el qual hem demostrat que $u_1 - v_1$ és arrel és independent de l'arrel escollida.
+
+\[ \beta_i = u_i - v_i = y_i - \frac{p}{3 u_i}, \]
+on $u_i$ és una de les arrels cúbiques de $z_i$ (en total n'hi haurà 3, ja que pel Teorema Fonamental de l'Àlgebra n'hi ha 3, i si n'hi ha menys, és perquè hi ha arrels repetides).
+
+\newpage
+
+\begin{Problem}
+ Trobeu les solucions de l'equació $X^3 - 6X - 6 = 0$ en $\mathbb{Q}$ i en $\mathbb{F}_{43}$.
+\end{Problem}
+
+\begin{itemize}
+ \item \textbf{Cas $\mathbb{Q}$}: Intentem factoritzar mitjançant Ruffini per trobar les arrels (sabem que si no es pot factoritzar per Ruffini, aleshores és irreductible i no existeix cap arrel a $\mathbb{Q}$):
+
+ \begin{center}
+ \begin{minipage}{\textwidth}
+ \begin{multicols}{2}
+ \[ \ruffini{1,0,-6,-6}{1}{1,1,-5}{1,1,-5,-11} \]
+ \[ \ruffini{1,0,-6,-6}{-1}{-1,1,5}{1,-1,-5,-1} \]
+ \[ \ruffini{1,0,-6,-6}{2}{2,4,-4}{1,2,-2,-10} \]
+ \[ \ruffini{1,0,-6,-6}{-2}{-2,4,4}{1,-2,-2,-2} \]
+ \[ \ruffini{1,0,-6,-6}{3}{3,9,9}{1,3,3,3} \]
+ \[ \ruffini{1,0,-6,-6}{-3}{-3,9,-9}{1,-3,3,-15} \]
+ \[ \ruffini{1,0,-6,-6}{6}{6,36,210}{1,6,30,204} \]
+ \[ \ruffini{1,0,-6,-6}{-6}{-6,36,-210}{1,-6,30,-216} \]
+ \end{multicols}
+ \end{minipage}
+ \end{center}
+
+ És a dir, no existeix cap solució de l'equació en $\mathbb{Q}$.
+
+ \item \textbf{Cas $\mathbb{F}_{43}$:}
+ \[ z_1, z_2 = \frac{6 \pm \sqrt{36 + 4 \frac{(-6)^3}{27}}}{2} = \frac{1}{2} \left( 6 \pm \sqrt{36} \cdot \sqrt{1 - \frac{24}{27}} \right) = \]
+ \[ = \frac{1}{2} \left( 6 \pm 6 \sqrt{1 - \frac{24}{27}} \right) = 3 \pm 3 \sqrt{\frac{3}{27}} = 3 \pm \sqrt{\frac{1}{9}} = 3 \pm 1 = 2, 4. \]
+
+ Ara busquem arrels cúbiques de $2$ i $4$ a $\mathbb{F}_{43}$. Són les següents:
+ \[ 20^3 = 2, \quad 32^3 = 2, \quad 34^3 = 2, \quad 13^3 = 4, \quad 35^3 = 4, \quad 38^3 = 4. \]
+ \[ u_1 = 20, \quad u_2 = 32, \quad u_3 = 34, \quad u_4 = 13, \quad u_5 = 35, \quad u_6 = 38. \]
+
+ Tenim que:
+ \[ v_i = \frac{p}{3 u_i} = \frac{-6}{3} u_i^{-1} = -2 u_i^{-1} \implies \]
+ \[ \implies \left\{ \begin{array}{l}
+ v_1 = -2 u_1^{-1} = -2 \cdot 28 = 30 \\
+ v_2 = -2 u_2^{-1} = -2 \cdot 39 = 8 \\
+ v_3 = -2 u_3^{-1} = -2 \cdot 19 = 5 \\
+ v_4 = -2 u_4^{-1} = -2 \cdot 10 = 23 \\
+ v_5 = -2 u_5^{-1} = -2 \cdot 16 = 11 \\
+ v_6 = -2 u_6^{-1} = -2 \cdot 17 = 9
+ \end{array} \right\} \implies \]
+ \[ \implies \begin{cases}
+ \beta_1 = u_1 - v_1 = 20 - 30 = 33, \\
+ \beta_2 = u_2 - v_2 = 32 - 8 = 24, \\
+ \beta_3 = u_3 - v_3 = 34 - 5 = 29, \\
+ \beta_4 = u_4 - v_4 = 13 - 23 = 33, \\
+ \beta_5 = u_5 - v_5 = 35 - 11 = 24, \\
+ \beta_6 = u_6 - v_6 = 38 - 9 = 29.
+ \end{cases} \]
+
+ Hem comprovat que efectivament és el mateix prendre $z_1$ que $z_2$ per tal de generar les 3 arrels.
+
+ Per tant, les arrels són:
+ \[ \beta_1 = 33, \quad \beta_2 = 24, \quad \beta_3 = 29. \]
+\end{itemize}
+
+\begin{Problem}
+ Considereu l'equació $X^3 + X - 2 = 0$ sobre $\mathbb{Q}$.
+
+ \begin{enumerate}[a)]
+ \item Trobeu les solucions \textit{a ull}.
+ \item Calculeu les solucions amb les fórmules de l'exercici 5 i deduïu la igualtat:
+ \[ \sqrt[3]{1 + \frac{2}{3} \sqrt{\frac{7}{3}}} + \sqrt[3]{1 - \frac{2}{3} \sqrt{\frac{7}{3}}}. \]
+ \item Comproveu que
+ \[ \left( \frac{1}{2} + \frac{1}{2} \sqrt{\frac{7}{3}} \right)^3 = 1 + \frac{2}{3} \sqrt{\frac{7}{3}}, \]
+ i utilitzeu aquesta igualtat per relacionar els resultats que heu obtingut als apartats anteriors.
+ \end{enumerate}
+\end{Problem}
+
+\textbf{Apartat a):} \\
+A ull veiem que una solució trivial és $X = 1$. Aleshores, factoritzant el polinomi (dividim $X^3 + X - 2$ entre $X - 1$) obtenim:
+\[ (X^3 + X - 2) = (X - 1)(X^2 + X + 2), \]
+on veiem que les altres 2 arrels no pertanyen als racionals, ja que els coeficients són tots estrictament positius.
+
+\textbf{Apartat b):} \\
+Calculem les solucions amb les fórmules de l'apartat 5:
+\[ z_{1, 2} = \frac{-q \pm \sqrt{q^2 + 4 \frac{p^3}{27}}}{2} = \frac{2 \pm \sqrt{4 + \frac{4}{27}}}{2} = 1 \pm \sqrt{1 + \frac{1}{27}} = \]
+\[ = 1 \pm \sqrt{\frac{28}{27}} = 1 \pm \frac{2}{3}\sqrt{\frac{7}{3}}. \]
+
+Aleshores:
+\[ u_1 = \sqrt[3]{1 + \frac{2}{3} \sqrt{\frac{7}{3}}} \implies v_1 = \sqrt[3]{- z_2} = - \sqrt[3]{1 - \frac{2}{3} \sqrt{\frac{7}{3}}}. \]
+
+Finalment, tenim que $u_1 - v_1$ és arrel:
+\[ u_1 - v_1 = \sqrt[3]{1 + \frac{2}{3} \sqrt{\frac{7}{3}}} + \sqrt[3]{1 - \frac{2}{3} \sqrt{\frac{7}{3}}}. \]
+
+Escollim encabir $\mathbb{Q}$ dins de $\mathbb{R}$ i alhora de $\mathbb{C}$ com a clausura algebraica per conveniència. Aleshores, mentre que una arrel de l'equació és racional (i per tant real), les altres dues són complexes. Aquesta arrel que hem trobat explícitament ($u_1 - v_1$) és real i, per tant, ha de ser igual 1 que és l'única arrel real.
+
+\textbf{Apartat c):}
+\[ \left( \frac{1}{2} + \frac{1}{2} \sqrt{\frac{7}{3}} \right)^3 = \frac{1}{8} \left( 1 + \sqrt{\frac{7}{3}} \right)^3 = \frac{1}{8} \left( 1 + 3 \sqrt{\frac{7}{3}} + \frac{\cancel{3} \cdot 7}{\cancel{3}} + \left( \sqrt{\frac{7}{3}} \right)^3 \right) = \]
+\[ = \frac{1}{8} \left( 8 + \sqrt{\frac{7}{3}} \left( 3 + \frac{7}{3} \right) \right) = \frac{1}{8} \left( 8 + \sqrt{\frac{7}{3}} \frac{16}{3} \right) = 1 + \frac{2}{3} \sqrt{\frac{7}{3}}. \]
+
+Observem que aquesta igualtat el que ens diu és que $\frac{1}{2} + \frac{1}{2} \sqrt{\frac{7}{3}}$ és una arrel tercera de $z_1$. Relacionant-lo amb l'apartat b), tenim que
+\[ \sqrt[3]{1 - \frac{2}{3} \sqrt{\frac{7}{3}}} = 1 - \frac{1}{2} + \frac{1}{2} \sqrt{\frac{7}{3}} = \frac{1}{2} - \frac{1}{2} \sqrt{\frac{7}{3}}, \]
+que és el conjugat.
+
+Veiem que sumant els dos conjugats efectivament obtenim 1, el que hem vist a l'apartat a).
+
+\newpage
+
+La resta de l'entregable (apartats 8-12) estan fets a mà.
+
+\end{document}
diff --git a/quad9/galois/labs/lab1/utils/.gitignore b/quad9/galois/labs/lab1/utils/.gitignore
new file mode 100644
index 0000000..26ba254
--- /dev/null
+++ b/quad9/galois/labs/lab1/utils/.gitignore
@@ -0,0 +1,2 @@
+cubs
+inverses
diff --git a/quad9/galois/labs/lab1/utils/Makefile b/quad9/galois/labs/lab1/utils/Makefile
new file mode 100644
index 0000000..4f5fdf3
--- /dev/null
+++ b/quad9/galois/labs/lab1/utils/Makefile
@@ -0,0 +1,7 @@
+all: inverses cubs
+
+inverses: inverses.cc
+ g++ inverses.cc -Wall -o inverses
+
+cubs: cubs.cc
+ g++ cubs.cc -Wall -o cubs
diff --git a/quad9/galois/labs/lab1/utils/cubs.cc b/quad9/galois/labs/lab1/utils/cubs.cc
new file mode 100644
index 0000000..ac064f9
--- /dev/null
+++ b/quad9/galois/labs/lab1/utils/cubs.cc
@@ -0,0 +1,9 @@
+#include <iostream>
+
+int main() {
+ int p = 43;
+ for (int i = 0; i < p; ++i) {
+ int a = (i*i*i) % p;
+ std::cout << i << "^3 = " << a << std::endl;
+ }
+}
diff --git a/quad9/galois/labs/lab1/utils/inverses.cc b/quad9/galois/labs/lab1/utils/inverses.cc
new file mode 100644
index 0000000..c54a019
--- /dev/null
+++ b/quad9/galois/labs/lab1/utils/inverses.cc
@@ -0,0 +1,13 @@
+#include <iostream>
+
+int main() {
+ int p = 43;
+ for (int i = 1; i < p; ++i) {
+ for (int j = 1; j < p; ++j) {
+ if ((i*j) % 43 == 1) {
+ std::cout << i << "^{-1} = " << j << std::endl;
+ break;
+ }
+ }
+ }
+}