{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Entiers de Gauss"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'ensemble $\\mathbb G=\\{x+iy, x,y\\in\\mathbb Z\\}$ est un sous-anneau du corps $\\mathbb C$ des nombres complexes. Il est appelé l'anneau des entiers de Gauss. Dans ce qui suit nous représenterons en Python les éléments de l'anneau $\\mathbb G$ par des couples $(x,y)$ d'entiers relatifs. Très précisément, le couple $(x, y)$ représente l'élément $x+iy\\in\\mathbb G$.\n",
    "\n",
    "Après avoir défini les opérations de l'anneau, on écrit une division euclidienne dans $\\mathbb G$. À partir de là, il est facile de décrire l'algorithme d'Euclide qui calcule le pgcd de deux entiers de Gauss."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Opérations dans $\\mathbb G$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Addition, soustraction, opposé, conjugué"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ces opérations s'écrivent sans difficultés."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add(z1, z2):\n",
    "    return (z1[0] + z2[0], z1[1] + z2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "add((1, 2), (3, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sub(z1, z2):\n",
    "    return (z1[0] - z2[0], z1[1] - z2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sub((1, 2), (3, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def oppose(z):\n",
    "    return (-z[0], -z[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "oppose((2, -3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def conjugue(z):\n",
    "    return (z[0], -z[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "conjugue((2, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Produit, carré du module, inverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ici encore, rien à dire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mult(z1, z2):\n",
    "    a = z1[0] * z2[0] - z1[1] * z2[1]\n",
    "    b = z1[0] * z2[1] + z1[1] * z2[0]\n",
    "    return (a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mult((1, 2), (3, 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def norme(z):\n",
    "    return z[0] ** 2 + z[1] ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "norme((1, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inverse(z):\n",
    "    if norme(z) == 1: return conjugue(z)\n",
    "    else: raise Exception('non inversible')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inverse((0, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Divisibilité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soient $a, b\\in\\mathbb G$. $b$ divise $a$ lorque le nombre complexe $\\frac a b\\in\\mathbb C$ est en fait dans $\\mathbb G$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On définit donc le quotient dans $\\mathbb C$ de deux entiers de Gauss. La fonction `quot_C` ci-dessous prend en paramètres $z_1, z_2\\in\\mathbb G$, $z_2\\ne 0$, et renvoie un couple $(z, n)$ où $z\\in\\mathbb G$ et $n\\in\\mathbb N^*$ sont tels que $\\frac {z_1} {z_2} = \\frac z n$. Rien de magique à cela, il suffit de remarquer que $\\frac{a+ib}{c+id}=\\frac{(ac+bd)+i(bc-ad)}{c^2+d^2}$.\n",
    "\n",
    "On a alors $z_2|z_1$ si et seulement si $n$ divise dans $\\mathbb Z$ la partie réelle et la partie imaginaire de $z$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quot_C(z1, z2):\n",
    "    a, b = z1\n",
    "    c, d = z2\n",
    "    return ((a * c + b * d, b * c - a * d), c * c + d * d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "quot_C((16, 2), (3, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est maintenant simple d'écrire la relation \"divise\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def divise (b, a):\n",
    "    z, n = quot_C(a, b)\n",
    "    u, v = z\n",
    "    return (u % n == 0) and (v % n == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "divise((1, 2), (5, 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "quot_C((5, 5), (1, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Une division euclidienne dans $\\mathbb G$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `quot_G`prend deux entiers de Gauss $a$ et $b$ et paramètres. Elle renvoie un entier de Gauss $q$ tel que $|\\frac a b - q| < 1$. Les entiers $x$ et $y$ qui apparaissent dans le corps de la fonction sont en fait $\\lfloor \\frac u n + \\frac 1 2\\rfloor$ et $\\lfloor \\frac v n + \\frac 1 2\\rfloor$, c'est à dire deux entiers proches de $\\frac u n$ et $\\frac v n$ de moins de $\\frac 1 2$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quot_G(a, b):\n",
    "    z, n = quot_C(a, b)\n",
    "    u, v = z\n",
    "    x = (2 * u + n) // (2 * n)\n",
    "    y = (2 * v + n) // (2 * n)\n",
    "    return (x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "quot_G((16, 2), (3, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `div_G` effectue la division euclidienne des entiers de Gauss $a$ et $b$, $b\\ne 0$. Elle renvoie un couple $(q, r)\\in\\mathbb G^2$ tel que $a=bq+r$ et $|r| < |b|$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def div_G(a, b):\n",
    "    q = quot_G(a, b)\n",
    "    r = sub(a, mult(q, b))\n",
    "    return (q, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "div_G((16, 2), (3, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Algorithme d'Euclide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Muni d'une division euclidienne, $\\mathbb G$ entre dans la famille très sélect des anneaux euclidiens. Dans un tel anneau on peut définir la notion de pgcd. L'algorithme d'Euclide, bien connu pour les entiers relatifs, y reste valide."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Calcul du pgcd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a, b):\n",
    "    while norme(b) != 0:\n",
    "        q, r = div_G(a, b)\n",
    "        a, b = b, r\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gcd((16, 2), (3, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Affichage formatté"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La même fonction, mais on renvoie la liste de tous les couples (quotient, reste) calculés par l'algorithme d'Euclide. On écrit d'abord une fonction qui renvoie une représentation de l'entier de Gauss $z$ sous la forme '$a+ib$'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_str(z):\n",
    "    x, y = z\n",
    "    if x == 0 and y == 0: return '0'\n",
    "    elif y == 0: return str(x)\n",
    "    elif x == 0: return str(y) + 'i'\n",
    "    elif y > 0:\n",
    "        if y == 1: return str(x) + '+i'\n",
    "        else: return str(x) + '+' + str(y) + 'i' \n",
    "    else:\n",
    "        if y == -1: return str(x) + '-i'\n",
    "        else: return str(x) + str(y) + 'i'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "to_str((-1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclid(a, b):\n",
    "    s = []\n",
    "    while norme(b) != 0:\n",
    "        q, r = div_G(a, b)\n",
    "        s.append((to_str(q), to_str(r)))\n",
    "        a, b = b, r\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "euclid((16, 2), (3, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Vérification : coefficients de Bézout"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout cela est bien, mais nos fonctions renvoient-elles des résultats corrects ? Une bonne façon de s'en persuader est d'écrire une fonction qui calcule les coefficients de Bézout. La fonction ci-dessous prend en paramètres deux entiers de Gauss $a$ et $b$. Elle renvoie un triplet $(u,v,\\delta)$ d'entiers de Gauss tels que $ua+vb=\\delta$ et $\\delta$ est un pgcd de $a$ et $b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bezout(a, b):\n",
    "    u1, v1, r1 = (1, 0), (0, 0), a\n",
    "    u2, v2, r2 = (0, 0), (1, 0), b\n",
    "    while norme(r2) != 0:\n",
    "        q, r = div_G(r1, r2)\n",
    "        u = sub(u1, mult(q, u2))\n",
    "        v = sub(v1, mult(q, v2))\n",
    "        u1, v1, r1 = u2, v2, r2\n",
    "        u2, v2, r2 = u, v, r\n",
    "    return (u1, v1, r1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = (1678665, 2443543)\n",
    "b = (-35543211, 1178967)\n",
    "u, v, r = bezout(a, b)\n",
    "print(u, v, r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant, calculons $au+bv-\\delta$ !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sub(add(mult(u, a), mult(v, b)),r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons bon espoir que tout n'est pas faux dans ce qui précède :-)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}