Shared2018-2019 / TP1-corrige.ipynbOpen in CoCalc
Authors: C Cazanave, FX D
Views : 21
Description: Corrige du TP1

L3 Algèbre effective — TP 1 du mardi 18 septembre 2018

Pgcd, algorithme d'Euclide et relations de Bezout

I - Algorithme d'Euclide

a) Trouver dans l'aide la fonction Sage qui permet de calculer le pgcd de deux entiers.

Faire quelques tests: pgcd(5,6)=? pgcd(0,6)=? pgcd(0,0)=?

En Sage, la fonction gcd permet de calculer le pgcd de deux entiers. On obtient l'aide associée en tapant help(gcd) ou bien gcd?.

In [1]:
gcd(5,6)
1
In [2]:
gcd?
1

Un premier objectif de ce TP est de reprogrammer cette fonction vous même, en utilisant l'algorithme d'Euclide.

b) Quelle fonction permet en Sage de calculer le reste dans une division euclidienne? Et le quotient?

Quelle est la division euclidienne de 1234 par 7?

On calcule le reste avec % et le quotient avec //.

In [9]:
1234%7
2
In [10]:
1234//7
176
In [11]:
1234==(1234//7)*7+(1234%7)
True

Pour 0mn0\leq m \leq n, quelle est la division euclidienne de mm par nn?

Quelle relation y a-t-il entre la division euclidienne de mm par nn et celle de m+nm+n par nn?

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).

Pour 0mn0\leq m \leq n, la division euclidienne de mm par nn est m=0n+m.m=0\cdot n + m. Si m=qn+rm=qn+r est la division euclidienne de mm par nn, alors m+n=(q+1)n+rm+n=(q+1)\cdot n+r est la division euclidienne de m+nm+n par nn. On en déduit le programme récursif ci-dessous.

In [6]:
def div(m,n): if (n==0): return "Division par zero" elif (m<n): return([0,m]) else: aux=div(m-n,n) return(aux[0]+1,aux[1])
In [8]:
div(510,3)
(170, 0)

c) Compléter la fonction ci-dessous pour qu'elle calcule le pgcd des arguments. Plusieurs approches sont possibles, dont:

  1. Une boucle
  2. Une fonction récursive

On présente les deux variantes.

In [11]:
def pgcd(m,n): while(n<>0): aux=n n=m%n m=aux return(m)
In [18]:
def pgcdRec(m,n): if (n==0): return m else: return pgcdRec(n,m%n)
In [19]:
pgcdRec(5,65)
5

Vérifier sur les exemples précédents.

In [ ]:

d) Quelle fonction en sage permet de trouver les coefficients d'une relation de Bézout? Donner une relation de Bézout entre 779 et 123.

Les coefficients de Bezout se calculent en utilisant la fonction xgcd.

In [ ]:
xgcd?
In [12]:
B=xgcd(779,123)
In [14]:
B[0]==779*B[1]+123*B[2]
True

Compléter la fonction suivante pour qu'elle calcule une relation de Bézout entre les arguments.

Plusieurs approches sont possibles, dont

  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 restes successifs dans l'algorithme d'Euclide
  2. Si rr est le reste de la division euclidienne de mm par nn, trouver un lien entre Bezout(m,n) et Bezout(n,r). En déduire une variante récursive.

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.

In [ ]:
In [2]:
def Bezout(m,n): L=[] while(n<>0): aux=n n=m%n L=L+[m//aux] m=aux i=len(L)-2 u=1 v=-L[i] while(i>0): i=i-1 aux=v v=u-L[i]*v u=aux return([u,v])
In [3]:
Bezout(779,123)
[1, -6]

Pour la méthode récursive, on remarque que si l'on injecte m=nq+r    r=mnqm=nq+r \iff r=m-nq dans une relation de Bézout pour nn et rr, disons un+vr=dun+vr=d, on obtient une relation de Bezout pour mm et nn de la forme d=un+v(mnq)=vm+(unv)nd=un+v(m-nq)=vm+(u-nv)n. D'où le programme récursif suivant:

In [5]:
def BezRec(m,n): if (n==0): return [1,0] else: aux=BezRec(n,m%n) return [aux[1],aux[0]-m//n*aux[1]]

Testez votre fonction.

In [12]:
BezRec(779,123)
[1, -6]
In [13]:
_[0]*779+_[1]*123
41
In [ ]:

II Équation diophantienne du type xm+yn=pxm+yn=p

a) Etant donnés trois entiers m,nm, n et pp, à quelle condition l'équation précédente admet-elle des solutions (x,y)(x,y) entières.

Ecrire un programme qui indique si cette équation a des solutions.

L'équation a des solutions ssi pp est multiple du pgcd(m,n)pgcd(m,n).

In [15]:
def existeSol(m,n,p): return (p%(gcd(m,n))==0)
In [17]:
existeSol(4,8,6)
False
In [ ]:

b) Ecrire un programme qui renvoie une solution particulière de l'équation.

**Une solution particulière s'obtient en multipliant une relation de Bézout entre mm et nn.

In [20]:
def solPart(m,n,p): b=xgcd(m,n) if (p% b[0] ==0): q= p//b[0] return [q*b[1],q*b[2]] else: return []
In [26]:
solPart(6,10,6)
[6, -3]

c)Ecrire un programme qui renvoie (sous forme de texte ou mieux?) l'ensemble de toutes les solutions.

In [37]:
def sol(m,n,p): b=xgcd(m,n) if (p% b[0] ==0): q= p//b[0] return "Les solutions sont:x="+str(q*b[1])+"+"+str(n/b[0])+"k et y="+str(q*b[2])+"-"+str(m/b[0])+"k." else: return ""
In [41]:
sol(4,6,8)
'Les solutions sont:x=-4+3k et y=4-2k.'

III Variante

Le but est d'implémenter la variante présentée lors du premier cours.

La première étape consiste à chercher (s'il existe) un inverse de m modulo n parmi les puissances de m.

L'entier mm est inversible modulo nn ssi mm et nn sont premiers entre eux. Le groupe (Z/nZ)×(\mathbf Z/n\mathbf Z)^\times est alors d'ordre φ(n)\varphi(n) et par le petit théorème de Fermat, on a mφ(n)11[n].m^{\varphi(n)-1}\equiv 1 [n].

In [13]:
def invMod(m,n): if gcd(m,n)==1: return m^(euler_phi(n)-1)%n else: return "Erreur: m n'est pas inversible mod n."
In [14]:
invMod(5,6)
5
In [ ]:

Comment obtient-on alors une solution particulière?

In [15]:
def Solpart2(m,n,p): d=gcd(m,n) m1=m//d n1=n//d u=invMod(m1,n1) v=(1-u*m1)/n1 return [u*p//d,v*p//d]
In [18]:
Solpart2(6,10,16)
[16, -8]

IV La suite de Fibonacci

On rappelle que la suite de Fibonacci est la suite linéaire récurrente définie par u0=1u1=1 et n2, un=un1+un2. u_0=1 \qquad u_1=1 \qquad \text{ et } \qquad \forall n \geq 2,\ u_{n}=u_{n-1}+u_{n-2}. Pour évaluer le 100ème terme de la suite, il est tentant d'implémenter la suite de manière récursive.

Faîtes le. Que remarquez-vous? Pourquoi?

In [ ]:
In [1]:
def fib(n): if n==0: return 1 elif n==1: return 1 else: return fib(n-1)+fib(n-2)
In [4]:
fib(10)
89

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 2n22^{n-2}. Pour n=100n=100, c'est trop grand!

In [5]:
2^100
1267650600228229401496703205376
In [ ]: