Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 02 - Questions de divisibilité

Divisibilité et division euclidienne

Le but de cette partie est de présenter les concepts de base de divisibilité et de division euclidienne dans l'ensemble des entiers relatifs.

[Note]

La plupart des résultats classiques d'arithmétique peuvent être tranposés à des structures algébriques bien plus générale que , appelées anneaux. On n'en parlera pas dans ce cours où nous nous limiterons aux entiers.

Rappels des notations ensemblistes

Pour être sûr de partir sur de bonnes bases, rappelons ici les notations classiques des ensembles d'entiers.

Notations

L'ensemble des entiers naturels, constitué donc des entiers positifs { 0 , 1 , 2 , 3 , . . . } , est noté . Ce même ensemble privé de l'élément 0 est noté * .

L'ensemble des entiers relatifs, constitué donc de tous les entiers { . . . , - 1 , - 2 , 0 , 1 , 2 , . . . } , est noté . Ce même ensemble privé de l'élément 0 est noté * .

Multiples et diviseurs

On s’intéresse simplement dans cette sous-partie aux divisions entre entiers qui "tombent juste". Il est clair par exemple que 4 divise 12, mais ne divise pas 13. Nous allons formaliser cela.

Définitions

Soient a , b éléments de . S'il existe un entier relatif q tel que a = b × q , on dit que :

  • b divise a.

  • b est un diviseur de a.

  • a est un multiple de b.

On note alors b | a .

[Note]

Cette notation avec une barre verticale est universelle et nous la respecterons.

En aucun cas elle ne représente un trait de fraction.

Comme toujours on omettra le symbole × sauf entre deux nombres, voire entre deux expressions parenthèsées. On écrira donc par exemple a = b q .

Example 1.1. Premières relations de divisibilités

Les relations suivantes sont immédiates :

  • 6 est un diviseur de 18 car 18 = 6 × 3 . Autre formulation, 18 est un multiple de 6.

  • - 13 | 221 car 221 = ( - 13 ) × ( - 17 ) .

  • Pour tout entier relatif a, a + 1 divise a 2 - 1 . En effet, on a l'égalité bien connue a 2 - 1 = ( a + 1 ) × ( a - 1 ) .


[Note]

L'ensemble des multiples de 0 est { 0 } , et l'ensemble de ses diviseurs est .

L'ensemble des multiples de 1 est , et l'ensemble de ses diviseurs est { - 1 ; 1 } .

[Note]

L'ensemble des multiples d'un entier relatif a est noté a par les algébristes. De façon savante on dit que a est l'idéal engendré par a dans l'anneau ( , + , × ) .

Moralement, si un entier relatif en divise un autre il est plus petit que celui-ci. Il faut bien sûr nuancer cela pour tenir compte des éventuels signes. Cette remarque conduit à ce résultat :

Propriété

Soient a , b éléments de .

Si b | a alors 0 < | b | | a | .

Démonstration

D'après les hypothèses, il existe un entier relatif q tel que a = b q . On a alors | b | = | a | | q | . Or q étant un entier relatif non nul, on a nécessairement | q | 1 . D'où 1 | q | 1 , ce qui prouve le résultat.

[Note]

L'ensemble des diviseurs d'un entier est donc fini. En effet, d'après la propriété précédente, les diviseurs d'un entier a sont nécessairement compris entre - | a | et | a | .

L'inégalité précédente permet facilement d'établir à quelles conditions deux entiers se divisent mutuellement.

Propriété

Soient a , b éléments de . On a l'équivalence suivante

( a | b et b | a ) ( a = b ou a = - b )

De la définition découlent également directement les propriétés suivantes :

Propriétés

Soient a , b , c éléments de .

  • Si a | b et b | c , alors a | c . Cela signifie que la relation de divisibilité est transitive.

  • Si a | b , alors pour tout entier relatif k, on a k a | k b .

  • Si a | b et a | c , alors pour tous entiers relatifs k et k , on a a | ( k b + k c ) .

Démonstration

Prouvons la propriété de transitivité. D'après les hypothèses, il existe q et q tels que b = a q et c = b q . On alors c = a q q , ce qui signifie bien que a | c .

Les autres résultats se démontrent de la même façon, en écrivant les hypothèses et en les exploitant directement.

Finissons cette sous-partie en donnant quelques critères de divisibilité, même si le lecteur les aura sans doute déjà rencontrés au cours de sa scolarité.

Propriétés

Un entier est divisible par 2 s'il se termine par 0 , 2 , 4 , 6 ou 8.

Un entier est divisible par 3 (resp. 9) si la somme de ses chiffres est divisible par 3 (resp. 9).

Un entier est divisible par 5 s'il se termine par 0 ou 5.

[Note]

On verra lors des séances d'exercices un critère bien plus élaboré de divisibilté par 11.

Division euclidienne

Quand une division entre entiers ne tombe pas juste, cela signifie qu’il y a un reste. Par exemple 4 ne divise pas 13, il y a un reste de 1. Nous allons formaliser cela dans cette sous-partie.

Le théorème suivant devrait rappeler des souvenirs au lecteur qui reconnaîtra la division qu'il effectuait sur les bancs de son école primaire.

Théorème

Soit a élément de , et b élément de * .

Il existe un unique couple d'entiers relatifs ( q , r ) vérifiant

a = b q + r et 0 r < b

Définitions

Avec les notations du théorème précédent, on appelle a le dividende, b le diviseur, q le quotient et r le reste dans la division euclidienne de a par b.

En pratique, pour déterminer le quotient et le reste, on distingue deux cas :

  • Si a est positif on lui retranche des multiples de plus en plus grands de b jusqu’à obtenir un reste strictement inférieur à b. Le quotient est alors le nombre de multiples de b retranchés.

  • Si a est négatif on lui additionne des multiples de plus en plus grands de b jusqu’à obtenir un reste strictement positif. Le quotient est alors l'opposé du nombre de multiples de b additionnés.

Le nom savant de cette méthode élémentaire est algorithme de la descente de Fermat.

En voici son implémentation en Python :

def descenteFermat(a,b):
    q, r = 0, a
    while r >= b:
        q += 1
        r -= b
    while r < 0:
        q -= 1
        r += b
    return q, r

La première boucle while gère le cas où a est positif, et la seconde celui où il est négatif.

Example 1.2. Premières divisions euclidiennes

On utilise la fonction précédente avec une valeur positive de a puis avec une valeur négative :

print(descenteFermat(27,12))
print(descenteFermat(-27,12))
(2, 3)
(-3, 9)

Cela correspond bien sûr aux deux divisions euclidiennes 27 = 12 × 2 + 3 et - 27 = 12 × ( - 3 ) + 9 .


[Note]

Un reste étant toujours positif, en aucun cas la division de - 27 par 12 est - 27 = 12 × ( - 2 ) + ( - 3 ) . Ce que l'on aurait pu naïvement penser connaissant la division euclidienne de 27 par 12.

Il faut bien comprendre que l’algorithme précédent donne en plus une preuve constructive de l’existence de la division euclidienne dans .

Il va nous permettre également de tester si un entier donné en divise un autre. Pour cela, il suffit de remarquer que si a est un élément de , et b un élément de * , alors b divise a si et seulement si le reste de la division euclidienne de a par b est nul.

Voici l'implémentation en Python de ce test de divisibilté :

def divisiblePar(a,b):
    q, r = descenteFermat(a,b)
    return r==0

On pourra alors déterminer facilement la liste des diviseurs d'un entier :

def listeDiviseurs(a):
    a = -a if a < 0 else a
    L = []
    for b in range(1,a+1):
        if divisiblePar(a,b):
            L.extend([b,-b])
    return L

Terminons cette sous-partie avec la présentation d'une méthode de preuve appelée raisonnement par disjonction des cas. Elle est basée sur la constatation suivante : après division euclidienne d’un entier relatif a par un entier naturel non nul b, les valeurs possibles des restes sont 0 , 1 , 2 , . . . , b - 1 . Ainsi, a peut s'écrire b k , b k + 1 , b k + 2 , . . . , b k + ( b - 1 ) avec k un élément de . Dans un problème de divisibilité par b, on pourra donc traiter chacun des b cas possibles.

[Note]

On retrouve le raisonnement par disjonction de cas présenté dans le cours 1SET, mais particularisé ici à des situations de divisibilité.

Example 1.3. Disjonction de cas

Dans un problème de divisibilité par 2, on pourra écrire tout entier a sous la forme 2k ou 2 k + 1 avec k élément de .

Dans un problème de divisibilité par 3, on pourra cette fois écrire tout entier a sous la forme 3k ou 3 k + 1 ou 3 k + 2 avec k élément de .


Exercice

On propose ici au lecteur un petit exercice d'application immédiate afin qu'il puisse tester sa capacité à utiliser un raisonnement par disjonction de cas.

Exercice corrigé

1.1.

Soit n élément de . Montrer que n × ( n 2 + 8 ) est divisible par 3. On raisonnera par disjonction des cas.

On distingue donc les trois cas :

  • Si n = 3 k , alors 3 | n donc 3 | n × ( n 2 + 8 ) .

  • Si n = 3 k + 1 , alors n 2 + 8 = 3 × ( 3 k 2 + 2 k + 3 ) , donc 3 | ( n 2 + 8 ) et donc 3 | n × ( n 2 + 8 ) .

  • Si n = 3 k + 2 , alors n 2 + 8 = 3 × ( 3 k 2 + 4 k + 4 ) , donc 3 | ( n 2 + 8 ) et donc 3 | n × ( n 2 + 8 ) .

Plus Grand Commun Diviseur

Dans cette partie nous allons définir la notion de PGCD, puis présenter le célèbre algorithme d'Euclide.

Définition du PGCD

Le PGCD, Plus Grand Commun Diviseur, de deux entiers relatifs est une notion que l’on manipule depuis toujours, parfois même inconsciemment.

Par exemple, lorsque l’on réduit une fraction à sa forme dite irréductible, on divise numérateur et dénominateur par leur PGCD :

90 120 = 3 × 30 4 × 30 = 3 4

Nous allons ici formaliser cette notion.

Définition

Soient a , b éléments de .

On appelle Plus Grand Commun Diviseur de a et b l’unique entier naturel d vérifiant à la fois

  1. d | a et d | b .

  2. Si c est un entier naturel tel que c | a et c | b alors c d .

On le notera d = PGCD ( a , b ) ou d = a b .

Première constatation, le PGCD porte bien son nom. C'est en effet un diviseur commun aux deux entiers (point 1 de la définition précédente) et c'est le plus grand (point 2).

[Note]

L'existence du PGCD résulte du caractère euclidien de : toute partie non vide majorée de admet un plus grand élément.

Example 1.4. Détermination empirique du PGCD

On veut calculer le PGCD de 18 et 48. On commence par chercher les diviseurs de ces deux entiers :

  • Les diviseurs de 18 dans sont 1 , 2 , 3 , 6 , 9 et 18.

  • Les diviseurs de 48 dans sont 1 , 2 , 3 , 4 , 6 , 8 , 12 , 16 , 24 et 48.

Les diviseurs communs de 18 et 48 dans sont donc 1 , 2 , 3 et 6. Le plus grand d'entre eux, et ainsi le PGCD de 18 et 48, est donc 6.


En pratique la méthode de l'exemple précédent devient vite inopérante, d’où la nécessité d’un algorithme de calcul.

Algorithme d'Euclide

Commençons par énoncer le célèbre lemme d'Euclide, issu de son oeuvre "Les éléments", Livre Ⅶ.

Lemme d'Euclide

Soient a , b , q , r éléments de .

Si a = b q + r , alors PGCD ( a , b ) = PGCD ( b , r ) .

Démonstration

Si c est un diviseur commun de a et b, puisque r = a - b q , il sera nécessairement également un diviseur de r.

De même, si c est un diviseur commun de b et r, il sera aussi un diviseur de a.

L’ensemble des diviseurs communs de a et b est donc égal à l’ensemble des diviseurs communs de b et r. Le résultat en découle.

Nous allons maintenant présenter l'algorithme d'Euclide permettant de calculer le PGCD de deux entiers naturels a et b.

En voici les étapes :

  1. Si b est non nul, diviser a par b. On note r le reste de cette division euclidienne.

  2. Remplacer a par b et b par r.

  3. Recommencer tant que cela est possible à partir de l’étape 1.

  4. Le PGCD est alors la dernière valeur non nulle de r.

Il faut bien comprendre que cet algorithme fonctionne grâce au lemme précédent, qui garantit la conservation de la valeur du PGCD d'étape en étape.

[Note]

L'hypothèse que a et b soient positifs n'est pas restrictive, car un entier et son opposé ont les mêmes diviseurs.

Example 1.5. Déroulement de l'algorithme d'Euclide

Calculons le PGCD de 142 et 38 avec l'algorithme d'Euclide :

142 = 38 × 3 + 28 38 = 28 × 1 + 10 28 = 10 × 2 + 8 10 = 8 × 1 + 2 8 = 2 × 4 + 0

On a donc PGCD ( 142 , 38 ) = 2 .


On va maintenant présenter deux implémentations en Python de cet algorithme, l'une itérative et l'autre récursive. Le lecteur n'aura aucunes difficultés à les comprendre, elles sont élémentaires.

Voici la version itérative de l'algorithme d'Euclide :

def PGCD(a,b):
    while b != 0:
        a, b = b, a%b
    return a

Et voici la version récursive de l'algorithme d'Euclide :

def PGCD(a,b):
    if b == 0:
        return a
    else:
        return PGCD(b,a%b)
[Note]

Dans les deux cas on a utilisé les fonctions natives du Python permettant de calculer le quotient et le reste d'une division euclidienne. Ce sont les opérateurs // et %.

On aurait tout aussi bien pu se servir de notre fonction maison "descenteFermat", implémentée dans la sous-partie 1.2.

Propriétés

Nous allons ici énoncer quelques propriétés classiques du PGCD.

Propriétés

Soient a , b éléments de .

  • Les diviseurs communs de a et b sont les diviseurs de PGCD ( a , b ) .

  • Si k est un entier relatif non nul, on a PGCD ( k a , k b ) = | k | × PGCD ( a , b ) .

  • Si d = PGCD ( a , b ) et si a , b sont des entiers naturels tels que a = d a et b = d b , alors PGCD ( a , b ) = 1 .

Démonstration

Les deux premières assertions peuvent se démontrer à l’aide de l’algorithme d’Euclide. La troisième découle de la seconde.

Example 1.6. Application des propriétés précédentes

On a vu dans un exemple précédent que PGCD ( 142 , 38 ) = 2 , donc :

  • Les diviseurs communs de 142 et 38 sont les diviseurs de 2, i.e. - 2 , - 1 , 1 et 2.

  • On a PGCD ( 71 , 19 ) = 2 .


Entiers premiers entre eux

La notion que nous allons définir dans cette sous-partie aura une grande importance dans la suite, en particulier quand nous étudierons certains algorithmes cryptographiques.

Définition

Deux entiers naturels non nuls sont dits premiers entre eux si leur PGCD est égal à 1.

On a bien sûr la formulation équivalente suivante :

Définition

Deux entiers naturels non nuls sont dits premiers entre eux si leurs seuls diviseurs communs sont - 1 et 1.

Example 1.7. Entiers premiers entre eux

  • PGCD ( 142 , 38 ) = 2 donc 142 et 38 ne sont pas premiers entre eux.

  • PGCD ( 142 , 37 ) = 1 donc 142 et 37 sont premiers entre eux.


Exercice

On propose ici au lecteur un petit exercice d'application immédiate de la notion de PGCD.

Exercice corrigé

1.1.

On désire paver une pièce rectangulaire de 3 , 52 mètres de largeur et de 9 , 28 mètres de longueur par des carrés dont le côté est un nombre entier de centimètres. Quelle doit être la mesure du côté pour utiliser un nombre minimal de carrés ? Quels sont les autres valeurs possibles du côté d’un carré ?

La mesure du côté doit être un diviseur commun de 352 et 928, et doit même être leur PGCD car on souhaite utiliser un nombre minimal de carrés.

Or on montre facilement à l’aide de l’algorithme d’Euclide que PGCD ( 352 , 928 ) = 32 . la mesure cherchée est donc 32 centimètres.

Les autres valeurs possibles sont les diviseurs communs de 352 et 928, i.e. les diviseurs de 32 : 1 , 2 , 4 , 8 et 16.

Théorème de Bézout

Le but de cette partie est de présenter un des théorèmes les plus célèbres de l'arithmétique. Il est dû au français Etienne Bézout (1730-1783).

Identité de Bézout

Le résultat qui suit montre que pour tout couple d'entiers relatifs, il existe une combinaison linéaire entière de ces deux nombres égale à leur PGCD.

Identité de Bézout

Soient a , b éléments de . Soit d = PGCD ( a , b ) .

Il existe deux entiers relatifs u et v premiers entre eux tels que a u + b v = d .

[Note]

Ce résultat est également connu sous le nom de théorème de Bachet.

Ces deux entiers ne sont pas uniques.

Nous ne démontrerons pas rigoureusement ce théorème, on se contera de voir et comprendre d'où viennent ces entiers, que l'on appelle aussi coefficients de Bézout.

Pour les déterminer, on commence par effectuer l'algorithme d'Euclide. On part ensuite de la dernière ligne où le reste est non nul (i.e. de la ligne donnant le PGCD), et on exprime successivement chacun des restes à l’aide de la ligne qui l’a produit. On obtient à la fin les coefficients u et v.

Voyons cela en pratique sur un exemple numérique, cela sera plus clair pour une fois qu'un long discours.

Example 1.8. Détermination pratique de coefficients de Bézout

Traitons le cas des entiers 142 et 38. Voici l'algorithme d'Euclide pour ces valeurs

142 = 38 × 3 + 28 38 = 28 × 1 + 10 28 = 10 × 2 + 8 10 = 8 × 1 + 2 8 = 2 × 4 + 0

On commence par exprimer le dernier reste non nul (i.e. le PGCD) à savoir 2

2 = 10 - 8 × 1

On remplace alors la valeur 8 à l'aide de son expression donnée par la ligne précédente : 8 = 28 - 10 × 2 .

On obtient

2 = 10 - ( 28 - 10 × 2 ) × 1

Ce qui après factorisation donne

2 = 28 × ( - 1 ) + 10 × 3

On remonte alors à la ligne précédente pour obtenir l'expression de 10 : 10 = 38 - 28 × 1 .

Après remplacement, on obtient

2 = 28 × ( - 1 ) + ( 38 - 28 × 1 ) × 3

Et donc

2 = 38 × 3 + 28 × ( - 4 )

On recommence de nouveau en remontant d'une ligne et en exprimant 28 : 28 = 142 - 38 × 3 .

On effectue le remplacement

2 = 38 × 3 + ( 142 - 38 × 3 ) × ( - 4 )

Puis la factorisation

2 = 142 × ( - 4 ) + 38 × 15

On a pris toutes les lignes une par une, notre calcul est terminé. On a plus qu'à constater que les valeurs u = - 4 et v = 15 conviennent.


Théorème de Bézout

Nous allons ici énoncer et démontrer le fameux théorème de Bézout, qui n'est en fait qu'un corollaire de l'identité précédente.

Théorème de Bézout

Soient a , b éléments de .

Les entiers a et b sont premiers entre eux si et seulement si il existe deux entiers relatifs u et v tels que a u + b v = 1 .

Démonstration

Si a et b sont premiers entre eux cela signifie que leur PCDG est égal à 1. L'existence des entiers relatifs u et v tels que a u + b v = 1 provient alors directement de l'identité de Bézout.

Réciproquement, s'il existe deux entiers relatifs u et v tels que a u + b v = 1 , les diviseurs communs de a et b seront nécessairement des diviseurs de 1. Ce qui prouve bien que a et b sont premiers entre eux.

Example 1.9. Application du théorème de Bézout

Pour tout entier naturel n, on peut affirmer que les entiers a = 2 n + 1 et b = 3 n + 2 sont premiers entre eux.

En effet, on voit facilement que - 3 a + 2 b = 1 . Le résultat découle alors du théorème de Bézout.


Exercice

On propose ici au lecteur un petit exercice d'application de la relation de Bézout.

Exercice corrigé

1.1.

Calculer pour commencer les coefficients de Bézout des entiers 7 et 9.

On dispose ensuite de deux sabliers, l’un de 7 minutes et l’autre de 9 minutes. Comment mesurer une durée de 1 minute ? En déduire comment procéder pour mesurer le temps de cuisson d’un œuf à la coque, puis plus généralement de toute durée.

Rappel : la durée de cuisson d’un oeuf à la coque est de 3 minutes.

Une simple application de l'algorithme d'Euclide montre que PGCD ( 7 , 9 ) = 1 et que 1 = 9 × ( - 3 ) + 7 × 4 .

Pour mesurer une durée de 1 minute, il faut donc d'abord déclencher les deux sabliers simultanément et les retourner dès la fin de leurs écoulements. Au bout de trois écoulements du sablier de 9 minutes, il restera 1 minute jusqu’à la fin du quatrième écoulement du sablier de 7 minutes.

Si l'on multiplie l'égalité 1 = 9 × ( - 3 ) + 7 × 4 par 3, on obtient 3 = 9 × ( - 9 ) + 7 × 12 . Pour mesurer le temps de cuisson d’un œuf à la coque on procède comme précédemment, avec cette fois neuf et douze écoulements.

Plus généralement, pour mesurer toute durée d on utilise l'égalité d = 9 × ( - 3 d ) + 7 × 4 d .

Théorème de Gauss

On va s'intéresser dans cette partie à un théorème de Carl Friedrich Gauss (1777-1855), et à son application à la résolution d'un certain type d'équations diophantiennes.

Théorème de Gauss

Le résultat suivant est donc dû à Gauss, et figure dans son livre "Disquisitiones arithmeticae" publié en 1801.

Théorème de Gauss

Soient a , b , c éléments de .

Si a | b c et si PGCD ( a , b ) = 1 , alors a | c .

Autrement dit, si a divise le produit de b et c, et si a et b sont premiers entre eux, alors a divise c.

Démonstration

D'après le théorème de Bézout, puisque a et b sont premiers entre eux, il existe deux entiers relatifs u et v tels que a u + b v = 1 .

En multipliant cette égalité par c, on obtient a u c + b v c = c .

Or par hypothèse a | b c , donc a | b v c . Il est de plus évident que a | a u c . Il en découle que a | c .

Application aux équations diophantiennes

Commençons par une définition afin de fixer le cadre de cette sous-partie.

Définition

Une équation diophantienne est une équation polynomiale à coefficients entiers dont on cherche les solutions parmi les nombres entiers.

Le nom donné à ces équations provient du mathématicien grec Diophante d'Alexandrie.

L’équation diophantienne la plus célèbre est celle posée par Pierre de Fermat (1601-1665)

x n + y n = z n

Le résultat conjecturé par Fermat est que si n > 2 , il n'existe pas d'entiers x , y , z vérifiant cette équation. Ce résultat rabaptisé Théorème de Fermat a mis plus de trois siècles à être démontré. Ce fut fait par le britannique Andrew Wiles (1953-) en 1994. Plusieurs générations de mathématiciens s’y étaient confrontés avant sans succès.

A noter que si n = 2 l'équation précédente a bien évidemment des solutions, il suffit de prendre n'importe quel triplet pythagoricien, par exemple 3 , 4 , 5 .

[Note]

Lors du congrès international des mathématiciens à Göttingen en 1900, David Hilbert (1862-1943) proposa une série de vingt-trois problèmes majeurs non encore résolus. Le dixième d'entre eux concerne les équations diophantiennes : existe t-il un algorithme déterminant s’il existe ou non une solution à une équation donnée ? La réponse est non, et cela a été démontré par Yuri Matiiassewitch en 1970.

Dans ce cours nous resterons assez modestes, puisque l'on ne traitera que le cas de certaines équations du premier degré à deux inconnues, i.e. des équations de la forme a x = b y .

Remarquons tout d'abord qu'il n'est pas restrictif de supposer que PGCD ( a , b ) = 1 , car si ce n'est pas le cas on peut toujours diviser l'équation par ce PGCD.

Pour plus de lisibilité, on va présenter la méthode de résolution sur un exemple. Ce n'est nullement un problème car en fait toutes les équations de ce type se traiteront de la même façon.

Considérons l'équation

12 x = 7 y

On a nécessairement 7 | 12 x . Or PGCD ( 7 , 12 ) = 1 donc d'après le théorème de Gauss 7 | x . Ainsi il existe un entier relatif k tel que x = 7 k .

En remplaçant x dans l'équation par cette expression on obtient alors 12 × 7 k = 7 y . Après simplification par 7, il vient y = 12 k .

On vient de montrer qu'une solution de cette équation est donc nécessairement de la forme x = 7 k , y = 12 k avec k entier relatif.

Réciproquement, il est immédiat de voir que tout couple de cette forme est solution de l'équation.

On en conclut que l'ensemble des solutions est

{ ( 7 k ,12 k ) , k }
[Note]

Lors de la séance d'exercices on s'intéressera à des équations un tout petit peu plus générales de la forme a x + b y = c . On verra comment les ramener à celles étudiées ci-dessus.

Corollaire du théorème de Gauss

On va énoncer et démontrer ici un résultat découlant directement du théorème de Gauss.

Corollaire du théorème de Gauss

Soient a , b , c éléments de .

Si a | c , b | c , et si PGCD ( a , b ) = 1 , alors a b | c .

Autrement dit, si a et b divisent c, et si a et b sont premiers entre eux, alors le produit de a et b divise c.

Démonstration

Puisque a et b divisent c, il existe deux entiers relatifs x et y tels que c = a x = b y . Ainsi a | b y . Or PGCD ( a , b ) = 1 , donc d'après le théorème de Gauss a | y . Il existe donc un entier relatif k tel que y = k a . En remplaçant y par cette valeur dans l'expression de c, on obtient alors c = b k a . Cela prouve bien que a b | c .

De ce corollaire on déduit sans peine les critères de divisibilité suivants.

Critères de divisibilités

Si un nombre entier est divisible par 2 et par 3, il est divisible par 6.

Si un nombre entier est divisible par 5 et par 12, il est divisible par 60.

[Note]

Sans l'hypothèse PGCD ( a , b ) = 1 ce résultat est bien sûr faux. Par exemple 12 est divisible par 2 et par 4 mais pas par 8.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels