{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# **L3 Algèbre effective — TP 1  du mardi 17 septembre 2019**\n",
    " \n",
    "## **Pgcd, algorithme d'Euclide et relations de Bezout**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## I La suite de Fibonacci"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "On rappelle que la suite de Fibonacci est la suite linéaire récurrente définie par \n",
    "$$ u_0=1 \\qquad u_1=1 \\qquad \\text{ et } \\qquad \\forall n \\geq 2,\\ u_{n}=u_{n-1}+u_{n-2}.$$\n",
    "Pour évaluer le 100ème terme de la suite, il est tentant d'implémenter la suite de manière récursive. \n",
    "\n",
    "Faîtes le. Que remarquez-vous? Pourquoi?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def fib(n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    elif n==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib(n-1)+fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "89"
      ]
     },
     "execution_count": 39,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Le calcul de ```fib(100)``` est trop long: en effet, l'implémentation récursive est ici particulièrement inappropriée puisque l'on refait beaucoup de fois les mêmes calculs. Le nombre d'appels de la fonction ```fib``` pour calculer ```fib(n)``` est de l'ordre de $2^{n-2}$. Pour $n=100$, c'est trop grand!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1267650600228229401496703205376"
      ]
     },
     "execution_count": 40,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2^100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On implémente donc de manière iétrative: on calcule tous les termes de la suite de $u_0$ jusqu'à $u_n$ en ne gardant en mémoire que les deux derniers termes.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def fib_it(n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    elif n==1:\n",
    "        return 1\n",
    "    else:\n",
    "        i=1\n",
    "        a=1\n",
    "        d=1\n",
    "        while (i<n):\n",
    "            i=i+1\n",
    "            aux=a\n",
    "            a=d\n",
    "            d=d+aux\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(573147844013817084101,\n",
       " 54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253848242007897109054754028438149611930465061866170122983288964352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104897203455577507196645425232862022019506091483585223882711016708433051169942115775151255510251655931888164048344129557038825477521111577395780115868397072602565614824956460538700280331311861485399805397031555727529693399586079850381581446276433858828529535803424850845426446471681531001533180479567436396815653326152509571127480411928196022148849148284389124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569365394873317659000206373126570643509709482649710038733517477713403319028105575667931789470024118803094604034362953471997461392274791549730356412633074230824051999996101549784667340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501)"
      ]
     },
     "execution_count": 42,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_it(100), fib_it(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On peut alors aller loin dans le calcul des termes...**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## **II -Pgcd**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "a) Trouver dans l'aide la fonction Sage qui permet de calculer le pgcd de deux entiers.\n",
    "\n",
    "Faire quelques tests: \n",
    "pgcd(5,6)=?\n",
    "pgcd(0,6)=?\n",
    "pgcd(0,0)=?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**En Sage, la fonction ```gcd``` permet de calculer le pgcd de deux entiers.\n",
    "On obtient l'aide associée en tapant ``` help(gcd)``` ou bien ``` gcd?```.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 43,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(5,6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 2,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Un premier objectif de ce TP est de reprogrammer cette fonction vous même, en utilisant l'algorithme d'Euclide."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "b) Quelle fonction permet en Sage de calculer le reste dans une division euclidienne? Et le quotient?\n",
    "\n",
    "Quelle est la division euclidienne de 1234 par 7?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On calcule le reste avec ```%``` et le quotient avec ```//```.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 44,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1234%7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "176"
      ]
     },
     "execution_count": 45,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1234//7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 46,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1234==(1234//7)*7+(1234%7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Pour $0\\leq m \\leq n$, quelle est la division euclidienne de $m$ par $n$?\n",
    "\n",
    "Quelle relation y a-t-il entre la division euclidienne de $m$ par $n$ et celle de $m+n$ par $n$?\n",
    "\n",
    "\n",
    "En utilisant les remarques ci-dessus, écrivez un programme **récursif** qui calcule la division euclidienne du premier argument par le second (s'il est non nul).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**Pour $0\\leq m \\leq n$, la division euclidienne de $m$ par $n$ est $$m=0\\cdot n + m.$$\n",
    "Si $m=qn+r$ est la division euclidienne de $m$ par $n$, alors $m+n=(q+1)\\cdot n+r$ est la division euclidienne de $m+n$ par $n$. On en déduit le programme récursif ci-dessous.**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def div(m,n):\n",
    "    if (n==0):\n",
    "        return \"Division par zero\"\n",
    "    elif (m<n):\n",
    "        return([0,m])\n",
    "    else:\n",
    "        aux=div(m-n,n)\n",
    "        return(aux[0]+1,aux[1])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(170, 2)"
      ]
     },
     "execution_count": 48,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "div(512,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "c) Compléter la fonction ci-dessous pour qu'elle calcule le pgcd des arguments.\n",
    "Plusieurs approches sont possibles, dont:\n",
    "1) Une boucle \n",
    "2) Une fonction récursive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On présente les deux variantes.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def pgcd(m,n):\n",
    "    a,b=m,n\n",
    "    while(b<>0):\n",
    "        aux=b\n",
    "        b=a%b\n",
    "        a=aux\n",
    "    return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def pgcdRec(m,n):\n",
    "    if (n==0):\n",
    "        return m\n",
    "    else:\n",
    "        return pgcdRec(n,m%n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 53,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pgcd(0,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**d-1.)** Pour évaluer la \"complexité\" du calcul du pgcd, on pourrait commencer par compter le nombre de divisions euclidiennes effectuées. Faîtes le.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On rajoute un compteur dans le programme précédent.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def pgcd(m,n):\n",
    "    compteur=0\n",
    "    a,b=m,n\n",
    "    while(b<>0):\n",
    "        compteur=compteur+1\n",
    "        aux=b\n",
    "        b=a%b\n",
    "        a=aux\n",
    "    return(a, compteur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 9)"
      ]
     },
     "execution_count": 56,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pgcd(fib(10),fib(9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(11, 4)"
      ]
     },
     "execution_count": 57,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pgcd(fib(10)-1,fib(9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 7)"
      ]
     },
     "execution_count": 58,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pgcd(fib(10)-2,fib(9))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On remarque que le nombre d'itérations semble assez chaotique: pour des entiers très proches, cela varie, et pas du tout linéairement.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**d-2)** Une façon d'améliorer la complexité ci-dessus est de ne pas utiliser des divisions euclidiennes *stricto sensu*, mais des divisions avec restes possiblement négatifs.\n",
    "Remarquer que si *a*>*b*>0 sont des entiers, alors il existe une division avec reste:\n",
    "\n",
    "*a=bq+r*, **avec |r|≤ b/2**\n",
    "\n",
    "(Noter  qu'ici, *r* est potentiellement négatif!) et qu'alors, on a *pgcd(a,b)=pgcd(b,|r|)*.\n",
    "\n",
    "Utiliser cette remarque pour proposer un calcul du pgcd plus rapide que le précédent et comparer le nombre d'opérations.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On commence par coder le nouveau reste de la division euclidienne sophistiquée.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def reste(m,n):\n",
    "    if (n==0):\n",
    "        return \"Division par zero\"\n",
    "    elif abs(m)<= abs(n)//2:\n",
    "        return m\n",
    "    else:\n",
    "        return reste(abs(m)-abs(n),n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 68,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reste(5,-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**On peut alors reprendre le même programme qu'avant, en utilisant juste la nouvelle fonction reste.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def pgcd2(m,n):\n",
    "    compteur=0\n",
    "    a,b=m,n\n",
    "    while(b<>0):\n",
    "        compteur=compteur+1\n",
    "        aux=b\n",
    "        b=reste(a,b)\n",
    "        a=aux\n",
    "    return(a, compteur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((-1, 5), (11, 3), (1, 5))"
      ]
     },
     "execution_count": 76,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pgcd2(fib(10),fib(9)),pgcd2(fib(10)-1,fib(9)),pgcd2(fib(10)-2,fib(9))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**La fonction pgcd2 a bien l'air meilleure. Pour tester plus, on tire au hasard quelques entiers et on compare les deux fonctions.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.00000000000000\n",
      "1.25000000000000\n",
      "1.12500000000000\n",
      "1.42857142857143\n",
      "1.60000000000000\n",
      "1.40000000000000\n",
      "1.83333333333333\n",
      "1.50000000000000\n",
      "1.00000000000000\n",
      "1.42857142857143\n",
      "1.42857142857143\n",
      "1.60000000000000\n",
      "1.50000000000000\n",
      "1.40000000000000\n",
      "1.00000000000000\n",
      "1.33333333333333\n",
      "1.37500000000000\n",
      "1.00000000000000\n",
      "1.25000000000000\n",
      "1.50000000000000\n",
      "1.14285714285714\n",
      "1.50000000000000\n",
      "1.14285714285714\n",
      "1.44444444444444\n",
      "1.33333333333333\n",
      "1.66666666666667\n",
      "1.16666666666667\n",
      "1.75000000000000\n",
      "1.22222222222222\n",
      "1.33333333333333\n",
      "1.00000000000000\n",
      "1.60000000000000\n",
      "1.00000000000000\n",
      "1.60000000000000\n",
      "1.33333333333333\n",
      "1.20000000000000\n",
      "1.00000000000000\n",
      "1.80000000000000\n",
      "1.50000000000000\n",
      "1.14285714285714\n",
      "1.40000000000000\n",
      "1.20000000000000\n",
      "1.25000000000000\n",
      "1.25000000000000\n",
      "1.25000000000000\n",
      "1.20000000000000\n",
      "1.20000000000000\n",
      "1.25000000000000\n",
      "1.50000000000000\n",
      "1.28571428571429\n",
      "1.16666666666667\n",
      "1.66666666666667\n",
      "1.00000000000000\n",
      "1.28571428571429\n",
      "1.50000000000000\n",
      "1.20000000000000\n",
      "1.33333333333333\n",
      "1.42857142857143\n",
      "1.14285714285714\n",
      "1.71428571428571\n",
      "1.57142857142857\n",
      "1.40000000000000\n",
      "1.42857142857143\n",
      "1.00000000000000\n",
      "1.42857142857143\n",
      "1.71428571428571\n",
      "1.33333333333333\n",
      "1.00000000000000\n",
      "1.00000000000000\n",
      "1.00000000000000\n",
      "1.20000000000000\n",
      "1.33333333333333\n",
      "1.33333333333333\n",
      "1.25000000000000\n",
      "1.00000000000000\n",
      "1.28571428571429\n",
      "1.25000000000000\n",
      "1.60000000000000\n",
      "1.20000000000000\n",
      "1.33333333333333\n",
      "1.14285714285714\n",
      "1.57142857142857\n",
      "1.66666666666667\n",
      "1.12500000000000\n",
      "1.00000000000000\n",
      "1.00000000000000\n",
      "1.44444444444444\n",
      "1.80000000000000\n",
      "1.55555555555556\n",
      "1.00000000000000\n",
      "1.00000000000000\n",
      "1.14285714285714\n",
      "1.42857142857143\n",
      "1.50000000000000\n",
      "1.33333333333333\n",
      "1.25000000000000\n",
      "1.60000000000000\n",
      "1.40000000000000\n",
      "1.33333333333333\n",
      "1.25000000000000\n"
     ]
    }
   ],
   "source": [
    "for i in range(100):\n",
    "    a=randint(1,10000)\n",
    "    b=randint(1,10000)\n",
    "    p1=pgcd(a,b)\n",
    "    p2=pgcd2(a,b)\n",
    "    print(p1[1]/(p2[1]+0.))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**La fonction pgcd2 semble bien meilleure.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "e) Implémenter une fonction *pgcdbin* utilisant l'algorithme binaire (faire une recherche si nécessaire)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def pgcdbin(m,n):\n",
    "    if (m==n):\n",
    "        return m\n",
    "    elif (m%2==0) and (n%2==0):\n",
    "        return 2*pgcdbin(m/2,n/2)\n",
    "    elif (m%2==0): # n est alors impair\n",
    "        return pgcdbin(m/2,n)\n",
    "    elif (n%2==0):\n",
    "         return pgcdbin(m,n/2)\n",
    "    elif (m>n):\n",
    "        return pgcdbin((m-n)/2,n)\n",
    "    else:\n",
    "        return pgcdbin((n-m)/2,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 3,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pgcdbin(45,15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "f) Quelle fonction en sage permet de trouver les coefficients d'une relation de Bézout?\n",
    "\n",
    "Donner une relation de Bézout entre 779 et 123."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**Les coefficients de Bezout se calculent en utilisant la fonction ```xgcd```.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "xgcd?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "B=xgcd(779,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B[0]==779*B[1]+123*B[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Compléter la fonction suivante pour qu'elle calcule une relation de Bézout entre les arguments.\n",
    "\n",
    "Plusieurs approches sont possibles, dont\n",
    "1) Calquer la méthode \"humaine\" qui consiste à remonter l'algorithme d'Euclide. Pour cela, il faut créer des listes en sage pour stocker les valeurs des quotients successifs dans l'algorithme d'Euclide\n",
    "2) Si r est le reste de la division euclidienne de m par n, trouver un lien entre Bezout(m,n) et Bezout(n,r).\n",
    "En déduire une variante récursive."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**Pour la première méthode, il faut créer la liste des quotients dans l'algorithme d'Euclide. Les listes sont codées par des suites entre crochets, par exemple ```[1,2,3]```. La fonction ```+``` permet de concaténer deux listes. On fait alors la remontée en changeant les coefficients au fur et à mesure.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def Bezout(m,n):\n",
    "    L=[]\n",
    "    while(n<>0):\n",
    "        aux=n\n",
    "        n=m%n\n",
    "        L=L+[m//aux]\n",
    "        m=aux\n",
    "    i=len(L)-2\n",
    "    u=1\n",
    "    v=-L[i]\n",
    "    while(i>0):\n",
    "        i=i-1\n",
    "        aux=v\n",
    "        v=u-L[i]*v\n",
    "        u=aux\n",
    "    return([u,v])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, -6]"
      ]
     },
     "execution_count": 5,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Bezout(779,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**Pour la méthode récursive, on remarque que si l'on injecte $m=nq+r \\iff r=m-nq$ dans une relation de Bézout pour $n$ et $r$, disons $un+vr=d$, on obtient une relation de Bezout pour $m$ et $n$ de la forme\n",
    "$d=un+v(m-nq)=vm+(u-nv)n$. D'où le programme récursif suivant:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def BezRec(m,n):\n",
    "    if (n==0):\n",
    "         return [1,0]\n",
    "    else:\n",
    "        aux=BezRec(n,m%n)\n",
    "        return [aux[1],aux[0]-m//n*aux[1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Testez votre fonction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, -6]"
      ]
     },
     "execution_count": 8,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "BezRec(779,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## III - Ecriture triadique (=en base 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Ecrire une fonction *triad* qui renvoie (sous forme de liste) l'écriture d'un entier en base *3*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def triad(n):\n",
    "    if (n<3):\n",
    "        return [n]\n",
    "    else:\n",
    "        u=n%3\n",
    "        return triad((n-u)/3)+[u]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 2]"
      ]
     },
     "execution_count": 12,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "triad(23)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath (stable)",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}