3 Enteros de Gauss.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Enteros de Gauss\n",
    "\n",
    "En este bloc mostramos los comandos básicos para trabajar con aritmética entera modular.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Antes de empezar vamos a cambiar la forma en la que se representan los complejos en GAP. GAP utiliza `E(4)` para referirse a $i$ (raíz cuarta de la unidad, de ahí la notación)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "InstallMethod(ViewString, [IsCyc], function(n) \n",
    "    local a,b;\n",
    "    a:=RealPart(n);\n",
    "    b:=ImaginaryPart(n);\n",
    "    if a=0 then \n",
    "        if b=1 then \n",
    "            return \"i\";\n",
    "        fi;\n",
    "        return Concatenation(String(b),\" i\");\n",
    "    fi;\n",
    "    if b=0 then \n",
    "        return String(a);\n",
    "    fi;\n",
    "    if b<0 then\n",
    "        return Concatenation(String(a),\" - \",String(-b),\" i\");\n",
    "    elif b=1 then\n",
    "        return Concatenation(String(a),\" + i\");\n",
    "    else\n",
    "        return Concatenation(String(a),\" + \",String(b),\" i\");\n",
    "    fi;\n",
    "    end\n",
    "    );"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "i"
      ]
     },
     "execution_count": 2,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i:=E(4);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cociente y resto \n",
    "\n",
    "Dados dos enteros de Gauss $a$ y $b$, el cociente y el resto se pueden obtener con `EuclideanQuotient` y `EuclideanRemainder`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "i"
      ]
     },
     "execution_count": 3,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EuclideanQuotient(3+i,1-2*i);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 4,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EuclideanRemainder(3+i,1-2*i);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1 + 2 i"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(-3+i)/(1+i);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En cualquier dominio euclídeo también se puede utilizar `QuotientRemainder`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ i, 1 ]"
      ]
     },
     "execution_count": 6,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "QuotientRemainder(GaussianIntegers,3+E(4),1-2*E(4));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos usar `Int` para obtener la parte \"entera\" de un cociente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2 - 3 i"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int((27-23*E(4))/(8+E(4)));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pero hay que tener en cuenta que éste no tiene por qué ser el cociente de la división. Vemoas qué norma tiene el resto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function( x ) ... end"
      ]
     },
     "execution_count": 8,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N:=x->x*ComplexConjugate(x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27 - 23 i"
      ]
     },
     "execution_count": 9,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "8 + i"
      ]
     },
     "execution_count": 10,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "8 - 1 i"
      ]
     },
     "execution_count": 11,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a:=27-23*i;\n",
    "b:=8+i;\n",
    "r:=a-Int(a/b)*b;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "65"
      ]
     },
     "execution_count": 12,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N(b);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "65"
      ]
     },
     "execution_count": 13,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N(r);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Máximo común divisor y mínimo común múltiplo. Coeficientes de Bézout\n",
    "\n",
    "El máximo común divisor de dos enteros de Guass (o más) puede ser calculado con el comando `Gcd`, y su mínimo común múltiplo con el comando `Lcm`, tal y como lo hacíamos con enteros racionales."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Gcd(3+i,-5-2*i);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9 + 33 i"
      ]
     },
     "execution_count": 15,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Lcm(3+i,-15-3*i);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si queremos conseguir los coeficientes de Bézout, podemos usar el comando `GcdRepresentation` (entre\n",
    "las muchas posibilidades que da `gap` para esto)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 2, 1 ]"
      ]
     },
     "execution_count": 16,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l:=GcdRepresentation(3+i,-5-2*i);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comprobemos el resultado"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 17,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l*[3+i,-5-2*i];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 5 - 25 i, 14 + 8 i, -3 ]"
      ]
     },
     "execution_count": 18,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "GcdRepresentation(10-5*i,15+10*i,18-5*i);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ecuaciones lineales\n",
    "\n",
    "Como ya sabemos, una vez resuelto el problema de encontrar los coeficientes de Bézout de un máximo común\n",
    "divisor de dos enteros de Gauss, tenemos también solución para resolver una ecuación lineal en dos variables. Lo\n",
    "único que tenemos que comprobar es si el término independiente es divisible por el máximo común\n",
    "divisor de los coeficientes, y luego multiplicar los coeficientes de Bézout por el factor apropiado\n",
    "para conseguir una solución particular.\n",
    "\n",
    "Si queremos resolver $4 x+ (3+3i) y= -1+5i$, hacemos lo siguiente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2 + 3 i"
      ]
     },
     "execution_count": 19,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(-1+5*i)/Gcd(4,3+3*i);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Luego una solución se obtiene fácilmente usando los coeficientes de Bézout."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "s:=GcdRepresentation(4,3+3*i)*(-1+5*i)/Gcd(4,3+3*i);;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos ver que el resultado es el correcto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1 + 5 i"
      ]
     },
     "execution_count": 21,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s*[4,3+3*i];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Factorizaciones y primos\n",
    "\n",
    "Para factorizar un entero en producto de primos podemos usar el comando `Factors`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1 - 1 i, 1 + i, 10 + 9 i ]"
      ]
     },
     "execution_count": 22,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Factors(20+18*i);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "También podemos saber si un número es primo usando el comando `IsPrime`. Pero tenemos que tener cuidado con especificar el anillo en que queremos comprobar la primalidad cuando se trate de enteros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 23,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsPrime(5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 24,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsPrime(GaussianIntegers,5);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Congruencias"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para resolver una ecuación en recurrencias podemos usar `GcdRepresentation` como hicimos arriba con una ecuación lineal. \n",
    "\n",
    "Si lo que queremos es resolver un sistema de congruencias de la forma\n",
    "$$\n",
    "\\begin{array}{l}\n",
    "x\\equiv a_1\\bmod m_1,\\\\\n",
    "\\dots\\\\\n",
    "x\\equiv a_n\\bmod m_n,\n",
    "\\end{array}\n",
    "$$\n",
    "en el caso de enteros de Gauss lo podemos hacer resolviendo una a una las ecuaciones y poniendo en la siguiente la solución para determinar el valor del parámetro.\n",
    "Así, para resolver\n",
    "$$\n",
    "\\begin{array}{l}\n",
    "x\\equiv i\\bmod 3,\\\\\n",
    "x\\equiv 1+i \\bmod 5+2i,\n",
    "\\end{array}\n",
    "$$\n",
    "hacemos lo siguiente."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "De la primera ecuación deducimos que $x=i+3t$ para algún $t\\in \\mathbb{Z}[i]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sustituimos en la segunda y obtenemos $i+3t\\equiv 1+i \\bmod{5+2i}$. Por lo que tenemos que resolver $3t\\equiv 1\\bmod{5+2i}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 25,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Gcd(3,5+2*i);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ -2 + i, 1 - 1 i ]"
      ]
     },
     "execution_count": 26,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "GcdRepresentation(3,5+2*i);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esto nos dice que el inverso de $3$ módulo $5+2i$ es $-2+i$. Así, nos queda $t\\equiv -2+i \\bmod{5+2i}$, o lo que es lo mismo, $t=-2+i+(5+2i)s$ para algún $s\\in \\mathbb{Z}[i]$. Por tanto, $x=i+3(-2+i+(5+2i)s)=-6+4i+(15+6i)s$ con $s\\in\\mathbb{Z}[i]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comprobemos que la solución particular $-6+4i$ está bien."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 27,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EuclideanRemainder(-6+4*i-i,3);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 28,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EuclideanRemainder(-6+4*i-(1+i),5+2*i);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP 4",
   "language": "gap",
   "name": "gap-4"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "GAP 4",
   "nbconvert_exporter": "",
   "pygments_lexer": "gap",
   "version": "4.dev"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}