San Vu Ngoc - IRMAR

Algorithme d'Euclide "étendu" qui fournit les entiers $u$ et $v$ tels que $au + bv = d$

Ici aussi on choisit d'abord une méthode récursive, la plus simple du point de vue mathématique, et aussi la plus facile à programmer.

Supposons par récurrence que $bu' + rv' = d = pgcd(b,r)$, alors en utilisant $a = bq + r$ on voit que $bu' + (a-bq)v' = d$ donc $$ av' + b(u' - qv') = d =pgcd(a,b).$$

Remarque: La suite des "restes" est la même que pour l'algorithme d'Euclide, donc on sait que ça termine. Et la complexité est la même.

In [1]:
def Bezout (a,b):  
    "cette fonction retourne (d,u,v) tel que au+bv=d"
    if b == 0:
        return (a, 1, 0)
    else:
        r = a % b
        q = a // b
        print("%d = %d*%d + %d" % (a,q,b,r))
        d,uu,vv = Bezout(b,r)
        print ("%d*(%d) + %d*(%d) = %d" % (a,vv, b, uu - vv*q, d))
        return (d, vv, uu - vv*q)
In [2]:
Bezout(1234,2020)

1234 = 0*2020 + 1234
2020 = 1*1234 + 786
1234 = 1*786 + 448
786 = 1*448 + 338
448 = 1*338 + 110
338 = 3*110 + 8
110 = 13*8 + 6
8 = 1*6 + 2
6 = 3*2 + 0
6*(0) + 2*(1) = 2
8*(1) + 6*(-1) = 2
110*(-1) + 8*(14) = 2
338*(14) + 110*(-43) = 2
448*(-43) + 338*(57) = 2
786*(57) + 448*(-100) = 2
1234*(-100) + 786*(157) = 2
2020*(157) + 1234*(-257) = 2
1234*(-257) + 2020*(157) = 2
Out[2]:
(2, -257, 157)

Vérifions:

In [3]:
-257*1234 + 157*2020
Out[3]:
2

Par Bachet-Bézout, on en déduit que (1234/2) et (2020/2) sont premiers entre eux:

In [4]:
-257*617 + 157*1010
Out[4]:
1
In [5]:
Bezout(617,1010)

617 = 0*1010 + 617
1010 = 1*617 + 393
617 = 1*393 + 224
393 = 1*224 + 169
224 = 1*169 + 55
169 = 3*55 + 4
55 = 13*4 + 3
4 = 1*3 + 1
3 = 3*1 + 0
3*(0) + 1*(1) = 1
4*(1) + 3*(-1) = 1
55*(-1) + 4*(14) = 1
169*(14) + 55*(-43) = 1
224*(-43) + 169*(57) = 1
393*(57) + 224*(-100) = 1
617*(-100) + 393*(157) = 1
1010*(157) + 617*(-257) = 1
617*(-257) + 1010*(157) = 1
Out[5]:
(1, -257, 157)
In [6]:
Bezout(600,124)

600 = 4*124 + 104
124 = 1*104 + 20
104 = 5*20 + 4
20 = 5*4 + 0
20*(0) + 4*(1) = 4
104*(1) + 20*(-5) = 4
124*(-5) + 104*(6) = 4
600*(6) + 124*(-29) = 4
Out[6]:
(4, 6, -29)

Version itérative

In [7]:
def BezoutI (a,b):
    "cette fonction retourne (d,u,v) tel que au+bv=d"
    uu, vv   = 1, 0
    u, v = 0, 1
    rr, r = a, b  # invariants de boucle: a*u + b*v = r  et  a*uu = b*vv = rr
    while r != 0:
        q = rr // r # on divise l'ancien reste "r(n-1)" (rr) par le reste "r(n)" (r)
        print ("On a %d = %d*%d + %d," % (rr, q, r, rr % r ))
        r, rr = rr % r, r
        u, uu = uu - q*u, u # on calcule les nouveaux coefficients u,v
        v, vv = vv - q*v, v
        print ("  donc %d = %d*(%d) + %d*(%d)." % (r, a, u, b, v))
    return (rr,uu,vv)
In [8]:
BezoutI(600,124)

On a 600 = 4*124 + 104,
  donc 104 = 600*(1) + 124*(-4).
On a 124 = 1*104 + 20,
  donc 20 = 600*(-1) + 124*(5).
On a 104 = 5*20 + 4,
  donc 4 = 600*(6) + 124*(-29).
On a 20 = 5*4 + 0,
  donc 0 = 600*(-31) + 124*(150).
Out[8]:
(4, 6, -29)
In [9]:
BezoutI(1234,2020)

On a 1234 = 0*2020 + 1234,
  donc 1234 = 1234*(1) + 2020*(0).
On a 2020 = 1*1234 + 786,
  donc 786 = 1234*(-1) + 2020*(1).
On a 1234 = 1*786 + 448,
  donc 448 = 1234*(2) + 2020*(-1).
On a 786 = 1*448 + 338,
  donc 338 = 1234*(-3) + 2020*(2).
On a 448 = 1*338 + 110,
  donc 110 = 1234*(5) + 2020*(-3).
On a 338 = 3*110 + 8,
  donc 8 = 1234*(-18) + 2020*(11).
On a 110 = 13*8 + 6,
  donc 6 = 1234*(239) + 2020*(-146).
On a 8 = 1*6 + 2,
  donc 2 = 1234*(-257) + 2020*(157).
On a 6 = 3*2 + 0,
  donc 0 = 1234*(1010) + 2020*(-617).
Out[9]:
(2, -257, 157)

Grand Théorème de Fermat

$$x^n + y^n = z^n, \quad n\geq 3$$

In [10]:
from IPython.display import HTML

HTML('<iframe width="560" height="315" src="https://www.youtube.com/embed/xNk0QYP0w5Q?rel=0&amp;&amp;showinfo=0" frameborder="0" allowfullscreen></iframe>')
Out[10]: