Retour | Index | Suite

Couples d'entiers premiers entre eux.

On dit que deux entiers relatifs a et b non nuls sont premiers entre eux si et seulement si PGCD(a ; b) = 1.

Remarques : Dans ℤ si a et b sont premiers entre eux alors les seuls diviseurs commun sont 1 et -1.

On considère deux entiers retatifs a et b non nuls. Si d désigne leur PGCD soit d = PGCD(a ; b)
alors il existe deux entiers relatifs a' et b' premiers entre eux tels que a = a'×d et b= b'×d.
Ainsi, en simplifiant par d, les fractions du type  a
b		  et  b
a
 conduisent respectivement aux fractions irréductibles  a'
b'		  et  b'
a'

Identité de Bézout.

On considère deux entiers retatifs a et b non nuls. Si d désigne leur PGCD soit d = PGCD(a ; b)
alors il existe deux entiers relatifs u et v tels que a×u + b×v = d.

Pour démontrer cette identité, il faut se place dans l'ensemble des entiers naturels strictement positifs qui peuvent se mettre sous la forme au + bv avec (u ; v) ∈ ℤ2. Cet ensemble est une partie non vide de ℕ donc qui adment un plus petit élément. On démontre alors que cet élément n'est autre que le PGCD de a et de b.

Théorème de Bézout.

On considère deux entiers retatifs a et b non nuls. Si a et b sont premières entre eux alors il existe deux entiers relatifs u et v tels que a×u + b×v = 1.

En effet, d'après l'identié de Bézout, il existe deux entiers relatifs u et v tels que au + bv = PGCD(a ; b). Or celui-ci est 1 donc au + bv = 1.
Réciproquement, si on a : au + bv = 1 alors le PGCD de a et de b divise toutes combinaisons linéaires de a et de b donc en particulier au + bv. Or au + bv = 1 donc le PGCD de a et de b doit diviser 1. Par conséquent PGCD(a ; b) = 1.

Pour déterminer les coefficients u et v, plusieurs méthodes sont disponibles.

  • Utilisation de la calculatrice.
  • Programme Python.
  • Remontée de l'algorithme d'Euclide.
  • Autre méthode utile.

    Remarques : Les coefficients de Bézout ne sont pas uniques !

    • Détermination des coefficients de Bézout.

  • Calculatrice.
    La méthode la plus simple est de remplacer par exemple u par x et v par y. On obtient ainsi, ax + by = 1 qui n'est autre qu'une équation cartésienne d'une droite.
    L'équation réduite de cette droite s'écrit y = (-ax +1)/b.
    En entrant dans la calculatrice la fonction f(x) = (-ax +1)/b, un tableau de valeurs avec un pas de 1 permet de repérer des couples d'entiers relatifs solutions.

    Exemple 1 : Déterminer au moins deux couples tels que 11u + 13v = 1.
    11 et 13 sont des nombres premiers, ils sont forcement premiers entre eux.
    On entre la fonction f(x)=(-11x +1)/13. On affiche le tableau des valeurs pour x compris entre -20 et 20 avec un pas de 1.
    On trouve pour cet intervalle 4 couples : (-20 ; 17) (-7 ; 6) (6 ; -5) et (19 ; -16).

    Remarques : Les valeurs succéssives de x présentent des différences de 13 et celles de y des différences de 11... Avec des valeurs de a et de b élevées cette méthode peut être plus délicate...
    Penser, alors à la fonction obtenue avec v = x et u = y, g(x) = (-bx + 1)/a.

  • Programme Python.
    Une alternative à cette méthode est un petit programme en Python...

     def test(a, b, n):
       d = gcd(a,b)
       for i in range (-n,n):
          for j in range (-n,n):
             if a*i+b*j == d:
                print(i,j)     		Si gcd n'est pas reconnu,
    ajouter from math import *
    ou changer gcd en pgcd 
    en ajoutant le programme
    ci-contre...     		 def pgcd(a, b):
       if b== 0: 
          return a 
       return pgcd(min(b,a),abs(b-a))      		 
     On peut ajouter en début de programme print(d) pour contrôle... ou en fin écrire print(i,j,d)
    Si aucune valeur n'est obtenue, augmanter n !

  • Algorithme d'Euclide.
    Un méthode efficace, mais qui peut être longue consiste à remonter l'algorithme d'euclide en isolant tous les restes, puis en les remplacant au fur et à mesure dans les expressions trouvées en partant de la fin c'est-à-dire du PGCD.

    Exemple 2 : Montrer que 31 et 65 sont premier entre eux, puis déterminer une solution particulière de l'équation 31u + 65v = 1.
    On remarque que 31 est un nombre premier (divisible que par 1 et lui-même) et 65 = 5×13 n'est pas divisible par 31 donc 31 et 65 sont premiers entre eux.
    65 = 2×31 + 3 3 = 65 - 2×31
    31 = 10×3 + 1 1 = 31 - 10×3
    3 = 3×1 + 0  
    En utilisant l'algorithme d'Euclide, le dernier reste non nul est 1, PGCD(31 ; 65)= 1 donc 31 et 65 sont bien premiers entre eux.
    On a : 1 = 31 - 10×3 où 3 est le reste de l'équalité précédente. On le remplace par son expression.
    On obtient 1 = 31 - 10×(65 - 2×31) soit encore 1 = 21×31 -10×65.
    Un solution particulière de l'équation proposée est (21 ; -10).