Sommaire

Mes pages

Ouverture

p. 1-11

Nombres complexes

Ch. 1

Nombres complexes, point de vue algébrique

Ch. 2

Nombres complexes, point de vue géométrique

Arithmétique

Ch. 3

Divisibilité dans Z

Testez le chapitre 100 % débloqué

Ch. 4

PGCD et applications

Ch. 5

Nombres premiers

Graphes et matrices

Ch. 6

Calcul matriciel et applications aux graphes

Ch. 7

Suites et matrices

Annexes

Exercices transversaux

Exercicesp. 238-243

Se préparer au Grand Oral

Grand oral

Présentation du Grand Oral

Grand oral

Conseils pour le Grand Oral

Méthode

Cahier d'algorithmique et de programmation

Page précédente

Chapitre 4

Activités

PGCD et applications

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

A
Problème de pavage

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Objectif : Découvrir et appliquer l'algorithme d'Euclide pour déterminer l'ensemble des diviseurs communs à deux entiers.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

On souhaite paver une surface rectangulaire de

250

cm par

70

cm à l'aide de carreaux carrés identiques de dimensions entières.

Mosaïque colorée de carreaux carrés. Chaque carreau est peint d'une couleur différente, créant un motif géométrique vibrant.

Patchanokk/Shutterstock

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Quelle condition la longueur

c

du côté d'un carreau doit-elle vérifier pour que les carreaux remplissent la surface sans qu'on ait besoin de les couper ?

Soient

a

b

deux entiers naturels non nuls avec

a > b

.
a) Montrer que les diviseurs communs à

a

b

sont exactement les diviseurs communs à

b

r

, où

r

désigne le reste de la division euclidienne de

a

par

b

Aide

Écrire la division euclidienne de

a

par

b

: elle permet d'écrire

r

comme combinaison linéaire de

a

b

b) On appelle

PGCD

a

b

le plus grand diviseur commun de

a

b

.
En déduire que le

PGCD

a

b

est égal au

PGCD

b

r

Pour tout réel

x

, on note

E (x)

la partie entière de

x

, l'unique entier tel que

E (x) ⩽ x < E (x) + 1

. On considère l'algorithme suivant.

1. 2. 3. 4. 5. 6. 7. 8. 9. a \leftarrow 250 b \leftarrow 70 r \leftarrow 250 - 70 \times E (\frac{250}{70}) Tant que r \neq = 0 faire : a \leftarrow b b \leftarrow r r \leftarrow a - b \times E (\frac{a}{b}) Fin Tant que Afficher b

a) À quoi les nombres

250 - 70 \times E (\frac{250}{70})

a - b \times E (\frac{a}{b})

(lignes 3 et 7) correspondent-ils ?

b) Exécuter cet algorithme à la main en recopiant et complétant le tableau suivant.

$a$	$250$
$b$	$70$
$r$

c) Pourquoi peut-on être sûr, sans l'exécuter, que cet algorithme se termine nécessairement ?

d) Que représente le nombre affiché en sortie ?
Que peut-on déduire sur les dimensions possibles du pavage ?

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Bilan

Cet algorithme de divisions successives porte aujourd'hui le nom d'Euclide. Euclide a en réalité décrit un algorithme voisin dans son livre Les Éléments pour expliciter une méthode de détermination du $PGCD$ de deux entiers naturels non nuls.

Soient $a$ et $b$ deux entiers naturels non nuls. Expliquer comment on peut déterminer l'ensemble des diviseurs communs à $a$ et $b$ connaissant leur $PGCD$ .

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

B
Un problème de Bachet

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Objectif : Utiliser le théorème de Bézout en « remontant » l'algorithme d'Euclide.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Deux bons compagnons ont 8 pintes de vin à partager entre eux également, lesquelles sont dans un vase contenant justement 8 pintes, et pour faire leur partage ils n'ont que deux autres vases dont l'un contient 5 pintes et l'autre 3. On demande comment ils pourront partager justement leur vin, ne se servant que de ces trois vases.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Photographie de chopes à bière en verre suspendues à un support en bois.

Vladimir Badaev/Shutterstock

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Remarque

Une pinte est une unité de mesure d'un volume.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Ce problème est posé par Bachet de Méziriac (1581-1638) dans Problèmes plaisants et délectables (1612). L'énoncé ci-dessus est tiré d'une réédition commentée de 1874. Une des méthodes qu'il donne consiste à remplir le vase

V_{5}

(de cinq pintes) et à le vider dans le vase

V_{3}

(de trois pintes) et ce jusqu'à obtenir une quantité de quatre pintes dans l'un des vases.
Le problème revient donc à déterminer combien de fois il faut remplir entièrement

V_{5}

et combien de fois il faut lui retirer trois pintes pour qu'il contienne quatre pintes.

Écrire le problème sous la forme

m x - p y = 4

avec

(m; p) \in N^{2}

et déterminer un couple

(x; y)

solution.

Bachet raisonne en prenant le problème par la fin : quatre pintes, ce sont cinq pintes dont on a retiré une pinte. Comment retirer une pinte ? Il suffit par exemple que le vase de trois pintes en contienne déjà deux.
a) Comment mesurer un volume de deux pintes avec les vases

V_{3}

V_{5}

b) Observer le schéma suivant et expliquer pourquoi à la fin du processus le vase

V_{5}

contient un volume de

2 B - 2 C

Schéma: algorithme répartissant des valeurs (V8, V5, V3) selon des règles mathématiques. Flèches indiquent le transfert de valeurs entre variables.

Cherchons maintenant à obtenir un volume de une pinte avec des vases de seize et neuf pintes.
a) Écrire l'algorithme d'Euclide pour déterminer le

PGCD

16

9

Soient

r_{1}

r_{2}

les restes des deux premières divisions euclidiennes obtenues.

b) À l'aide de la troisième division euclidienne, écrire le nombre

1

comme combinaison linéaire de

r_{1}

r_{2}

c) À l'aide de la deuxième division euclidienne, écrire le nombre

2

comme combinaison linéaire de

9

r_{1}

, puis justifier comment obtenir

1 = 7 \times 4 - 3 \times 9

d) En déduire une combinaison linéaire de

9

16

égale à

1

. Conclure.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Bilan

Le théorème de Bézout indique que si le $PGCD$ de deux entiers naturels $a$ et $b$ est $1$ , alors il existe un couple d'entiers relatifs $(u; v)$ tel que $au + bv = 1$ .
En prenant $a = 12$ et $b = 5$ et en s'appuyant sur le raisonnement de la question
3
, expliciter une démarche permettant de trouver $u$ et $v$ tels que $12 u + 5 v = 1$ . Ce couple est-il unique ?

Page suivante

Nombres complexes, point de vue algébrique

Nombres complexes, point de vue géométrique

Divisibilité dans Z

PGCD et applications

Nombres premiers

Calcul matriciel et applications aux graphes

Suites et matrices

Cahier d'algorithmique et de programmation

PGCD et applications

AProblème de pavage

BUn problème de Bachet

Remarque

A
Problème de pavage

B
Un problème de Bachet