Arithmétique : Chapitre 2

Page 1 sur 6

Partie A : Plus Grand Commun Diviseur / Théorème de Bachet-Bézout / Théorème de Gauss

I Le Plus Grand Commun Diviseur 1°/ Diviseurs communs à deux entiers :

a) Problème de pavage

On veut paver une pièce rectangle de dimensions 21m et 15m par des carrés de côté un nombre entier de taille maximale. ………………………………………………………………………………………………………………………………………………………………………………………………………….. ………………………………………………………………………………………………………………………………………………………………………………………………………….. …………………………………………………………………………………………………………………………………………………………………………………………………………..

b) Diviseurs communs – PGCD

Définition : Soient et deux entiers. On note l’ensemble des diviseurs communs à et . Remarques : * Les diviseurs communs à 0 et sont les diviseurs de pour tout .

* Pour tout

Proposition - Définition et ont un nombre fini de diviseurs, donc il en existe un plus grand ou égal à tous les autres Le plus grand commun diviseur à est appelé le PGCD de et de ,

Il est noté :

Exemples :

Remarque : PGCD(a ; b).

Proposition : si et seulement si divise . Démo : ……………………………………………………………………………………………………………………………………………………………………………………………….. ………………………………………………………………………………………………………………………………………………………………………………………………………….. …………………………………………………………………………………………………………………………………………………………………………………………………………..

2°/ PGCD et algorithme d’Euclide :

a) L’algorithme d’Euclide

Lemme d’Euclide désignent des entiers relatifs non nuls.

Si Démo :

Montrons que :

Montrons que : Soit ………………………………………………………………………………………….

Montrons que : Soit ………………………………………………………………………………………….

Ainsi on a et donc ( raisonnement par double inclusion )

On déduit ainsi que Remarque : dans le lemme ci-dessus on n’a pas la condition car elle n’est pas nécessaire, mais l’écriture ressemble à celle de la division euclidienne de par car c’est dans ce cadre-là qu’on va utiliser le lemme.

Arithmétique : Chapitre 2

Page 2 sur 6

Algorithme d’Euclide : a IN* et b IN*, avec a > b. On remplace par des couples de nombres de plus en plus petits, qui ont le même ensemble de diviseurs communs

Opération reste commentaire

On divise a par b Si r0 ≠ 0, on divise b par r0 Si r1 ≠ 0, on divise r0 par r1

⋮ Si rn – 1 ≠ 0, on divise rn – 2 par rn – 1

Si rn ≠ 0, on divise rn – 1 par rn

r0 r1 r2 ⋮ rn 0

0 r0 < b et PGCD(a ; b) = PGCD(b ; r0) 0 r1 < r0 et PGCD(b ; r0) = PGCD(r0 ; r1) 0 r2 < r1 et PGCD(r0 ; r1) = PGCD(r1 ; r2)

⋮ 0 rn < rn – 1 et PGCD(rn – 2 ; rn – 1) = PGCD(rn – 1 ; rn)

PGCD(rn – 1 ; rn) = rn

Ci-dessus, on note rn le dernier reste non nul. On trouve forcément un reste nul, en effet, les restes sont des entiers positifs qui vont en décroissant strictement ( 0 < et :

Propriété Si ne divise pas , le PGCD des entiers naturels non nuls est égal au dernier reste non nul obtenu par l’algorithme d’Euclide. Un exemple : recherche du PGCD de 1078 et 322 à l’aide de l’algorithme d’Euclide. On écrit les divisions euclidiennes successives : 1078=322x …… + …… PGCD(1078,322)=PGCD(……,……) …… = …… x …… + …… PGCD(……,……)=PGCD(……,……) …… = …… x …… + …… PGCD(……,……)=PGCD(……,……) …… = …… x …… + …… PGCD(……,……)=PGCD(……,……) Le dernier reste non nul de l’algorithme d’Euclide est …… donc PGCD(1078,322) = …… TICE : Algorithme d’Euclide sur la calculette : Savoir faire 5 p 49 Algorithme d’Euclide sur un tableur : Savoir faire 6 p 49 Visualisation géométrique de l’algorithme d’Euclide ( histoire ) : problème 4 p 45

b) Conséquences

Proposition : Les diviseurs communs à deux entiers relatifs non nuls et sont les diviseurs de . Preuve : En reprenant les notations de l’algorithme d’Euclide, le lemme d’Euclide nous donne les égalités suivantes :

( car divise )

Proposition : Si on multiplie deux entiers naturels non nuls par un même entier naturel , leur est multiplié par soit :

Démo :

Si ne divise pas : on écrit l’algorithme d’Euclide relatif au PGCD de et :

avec et avec et avec et ………………………………… avec et avec Le dernier reste non nul est donc On multiplie chaque égalité de division euclidienne par ainsi que les inégalités grâce aux règles connues ce qui donne : avec et

Arithmétique : Chapitre 2

Page 3 sur 6

avec et avec et ………………………………… avec et avec Conclusion : ……………………………..……………………………………………………………………………………………………………………………………………………… ……………………………..…………………………………………………………………………………………………………………………………………………………………………. ……………………………..…………………………………………………………………………………………………………………………………………………………………………. ……………………………..…………………………………………………………………………………………………………………………………………………………………………. ……………………………..………………………………………………………………………………………………………………………………………………………………………….

Si divise : ………………………………………………………………………………………………………………………………………………………………………. ……………………………..…………………………………………………………………………………………………………………………………………………………………………. Un exemple : Corollaire : Si est un entier naturel non nul, diviseur commun à et , alors :

Un exemple :

3°/ PGCD et décomposition en facteurs premiers

Proposition : a et b désignent deux entiers supérieurs ou égaux à 2. p1, p2, …, Pn sont des facteurs premiers figurant dans l’une ou l’autre des décompositions de a et b :

a =

… et b =

…

, avec α1, α2, …, αn, β1, β2, …, βn entiers naturels.

Le PGCD de a et b est égal au produit des facteurs premiers communs aux décompositions de a et b, chacun d’eux étant affecté du plus petit exposant avec lequel il figure dans la décomposition de a et b.

Ex : Si a = 2

2 × 5

2 × 7 et b = 2

3 × 5 × 11, alors PGCD(a ; b) =

II Le théorème de Bachet- Bézout

1) Un problème de chiffrement : 6 p 51

Sur feuille annexe

2) Théorème de Bachet-Bézout

a) Nombres premiers entre eux

Définition : Dire que deux nombres entiers non nuls sont premiers entre eux signifie que leur PGCD est égal à 1. Exemples : 25 et 27 , 7 et 5 Proposition : (Quotient de deux entiers non nuls par leur PGCD) désignent deux entiers relatifs non nuls. Si , alors il existe des entiers relatifs et premiers entre eux tels que

( Les nombres

et

sont premiers entre eux)

Démo : ………………………………………………………………………………………………………………………………………………………………………………………… …………………………………………………………………………………………………………………………………………………………………………………………………………….

Arithmétique : Chapitre 2

Page 4 sur 6

Corollaire : Si on divise numérateur et dénominateur d’une fraction

par on obtient une fraction irréductible.

b) Le théorème

Deux entiers relatifs non nuls sont premiers entre eux si, et seulement si, il existe des entiers relatifs tels que Démo : : supposons qu’ il existe des entiers relatifs tels que Soit alors divise et divise donc ……………………….……………………………………………………………………………… : Supposons

donc ou .

donc ou .

Si et sont des entiers naturels, on suppose par exemple que et ne divise pas . ( l’autre cas est identique à traiter)

L’algorithme d’Euclide s’écrit :

……. avec .

D’où, r0 = q0 = u0 + v0 avec u0 = 1 et v0 = – q0

r1 = – r0 q1 = + ( q0) × (– q1) = × (– q1) + × (1 + q0 q1) = u1 + v1 avec u1 = – q1 et v1 = 1 + q0 q1 En réitérant ce procédé, on montre que tous les restes rk, avec 0 , obtenus dans l’algorithme d’Euclide s’écrivent sous la forme rk = uk + vk, où uk et vk sont des entiers relatifs qui s’expriment en fonction de q0, q1, …, qk, et en particulier le dernier reste non nul rn qui est égal à 1.

Les autres cas, par exemple et se ramènent aux cas précédents : et étant entiers naturels,

il existe un couple d’entiers relatifs tels que

Il existe donc des entiers relatifs et tels que Remarque :

Le couple n’est pas unique. Par exemple, pour et , on obtient PGCD(3 ; 2) = 1. Or, 1 = 3 × 1 + 2 × (– 1) d’où et ou 1 = 3 × (– 1) + 2 × 2 d’où et Exemple:

Déterminer un couple d’entiers tels que . 1/ on écrit l’algorithme d’Euclide ; 2/ on isole les restes ( on exprime chaque reste en fonction de 29 et 11 (feuille annexe) Exemple: désigne un entier naturel non nul. Appliquer le théorème à et , puis à et . ………………………………………………………………………………………………………………………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………………………………………………………………………………………..

Arithmétique : Chapitre 2

Page 5 sur 6

3) Identité de Bézout

Proposition : désignent deux entiers relatifs non nuls. Si , alors il existe des entiers relatifs tels que

Preuve : D’après ce qui a été vu précédemment si on pose

et

alors . Donc

……..…..…..…..…..…..…..…..… …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. Histoire : Etienne Bézout rédige en 1763 un cours de mathématiques qui deviendra le Cours de mathématiques à l'usage des gardes du pavillon et de la marine. En 1768, il devient examinateur des élèves du corps de l'artillerie et rédige un manuel de mathématiques qui devient le livre de chevet des candidats au concours de l'École Polytechnique

III Théorème de Gauss

1) Théorème et désignent trois entiers relatifs non nuls. Si divise le produit et si est premier avec , alors divise Démo : …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..………. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. Remarque : Vérifier que est premier avec car peut diviser en ne divisant ni , ni Par exemple, 6 divise 300 , or 300 = 15 × 20 et Un problème : Dans une classe de moins de 38 élèves, la moyenne des notes des filles est 11,375 ; celle des notes des garçons est 10,5 et la moyenne de la classe est 10,8. L’objectif est de déterminer le nombre d'élèves dans cette classe. 1. On note le nombre de garçons et le nombre de filles, montrer que le couple vérifie l'équation . 2. Calculer , en déduire que vérifie l'équation . En utilisant le théorème de Gauss, montrer que est un multiple de 23 et que est un multiple de 12. 3. En déduire la solution du problème. Histoire : Johann Carl Friedrich Gauss (1777-1855) surnommé le prince des mathématiciens est considéré comme l'un des plus grands mathématiciens de tous les temps. Il n'a publié de son vivant qu'une partie infime de ses découvertes, la postérité découvrit la profondeur et l'étendue de son œuvre grâce à son journal intime, en 1898.

2) Conséquences Propriété :

et désignent des entiers relatifs non nuls et un nombre premier. Si divise le produit alors divise ou divise .

Démo : …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..………. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..

Arithmétique : Chapitre 2

Page 6 sur 6

Propriété : désignent des entiers relatifs non nuls Si et sont premiers entre eux et si chacun d’eux divise , alors divise . Démo : …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..………. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. …..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..…..….. Ex 1 : 5 et 9 sont premiers entre eux et divisent 1 035, alors . Ex 2 : Démontrer que 6 divise avec IN. Application des théorèmes de Gauss et Bézout : les équations diophantiennes Une jeune femme achète des CD et des DVD pour un total de 162 €. Sachant que le prix de chaque CD est 17 € et que le prix de chaque DVD est 20 €, on veut déterminer le nombre de CD et le nombre de DVD qu’elle a achetés. 1. On note le nombre de CD et le nombre de DVD ; montrer que et vérifient l'équation :

: . Une équation de ce type est appelé équation diophantienne. 2. En utilisant le théorème de Bézout, montrer que l'équation admet des solutions. 3. Montrer que est une solution particulière de l'équation . 4. Montrer que l'équation est équivalente à l’équation (E’) . 5. En utilisant le théorème de Gauss, déterminer les solutions de (E') et donc celles de . 7. Sachant que et déterminer la solution du problème. Remarque : variante de la question 3. Ici la solution particulière est fournie il n’y a plus qu’à vérifier. Dans le cas contraire il faut utiliser l’algorithme des restes de la démonstration du théorème de Bachet-Bézout.