bezout.py

""" bezout.py
"""
#! /usr/bin/python3
# -*- coding: utf-8 -*-

# calcul des coefficients de Bezout : PGCD(a, b) = a u + b v
#
# principe : les diviseurs communs à a et b
#   divisent aussi le reste : r = a - b q
# on remplace a par r
# et on recommence : diviseurs communs à b et r . . .
# voir aussi : pgcd.py

import sys
import math

def pgcd(a, b):
    # calcul des coefficients de Bezout : PGCD = u a + v b
    if type(a) != int :
        print("erreur type a")
        sys.exit(1)
    a0 = a
    b0 = b
    # a = b q0+ r0
    #   r0 = a * 1 + b * (-q0) = a u0 + b v0
    # b = r0 q1+ r1
    #   r1 = b - r0 q1 = a u1 + b v1
    #   avec u1 = (-q1) u0 ; et v1 = (-q1) v0 + 1
    # quand rn = 0 donc pgcd = r(n-1)
    (u0, v0) = (1, 0) # a = u0 a + v0 b
    (u1, v1) = (0, 1) # b = u1 a + v1 b
    r = b
    while r != 0 :
        # division euclidienne : a = b q + r
        r = a % b     # reste de la division a / b ; aussi a modulo b
        # r est divisible par le PGCD(a, b)
        # division euclidienne : q = partie entière du quotient
        q = a // b
        print(r, q)
        
        # on met r sous la forme : r = u a + v b
        # r = a - b q = u0 a + v0 b - q (u1 a + v1 b)
        # r = (u0 - q u1) a + (v0 - q v1) b
        (u2, v2) = (u0 - q * u1, v0 - q * v1)

        # bascule pour l'itération suivante :
        a = b
        (u0, v0) = (u1, v1)
        b = r
        (u1, v1) = (u2, v2)
    # print(a, (u0, v0), (u1, v1))
    # print(a0 * u0 + b0 * v0)
    # print(a0 * u1 + b0 * v1)
    return a, (u0, v0)

# nombres premiers entre eux (exemple : nombres de Fibonacci)
a = 144
b = 89
(x, (u, v)) = pgcd (a, b)
print("pgcd =", x)
print("Bezout :", a, "*(", u, ") +", b, "*(", v, ") =", a * u + b * v )

a = 2*3*5*7*17
b = 2*3*11*13*19
(x, (u, v)) = pgcd (a, b)
print("pgcd =", x)
print("Bezout :", a, "*(", u, ") +", b, "*(", v, ") =", a * u + b * v )

"""
"""