Mstsspe 2016
Mstsspe 2016
Mstsspe 2016
M AT R I C E S e t S U I T E S • ARITHMÉTIQUE
erm
S
Delphine ARNAUD
Lycée Dominique Savio,
Douala
Bruno CASAVECCHIA
Lycée Dominique Savio,
Douala
Paul MILAN
Lycée d’adultes de la Ville
de Paris
Environnement numérique et
relectures réalisés par l’association
SOMMAI RE
ARITHMÉTIQUE
■ AR1 MULTIPLES. DIVISION EUCLIDIENNE. CONGRUENCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1. Avant-propos
2. Multiples et diviseurs dans ℤ
3. La division euclidienne
4. Congruence
■ AR2 PGCD. THÉORÈMES DE BÉZOUT ET DE GAUSS ............................................ 27
1. Plus grand commun diviseur
2. Théorème de Bézout
3. Le théorème de Gauss et son corollaire
4. Équation diophantienne ax + by = c
■ AR3 LES NOMBRES PREMIERS ............................................................................ 51
1. Définition et propriétés
2. Décomposition, diviseurs d’un entier
Dans cette partie, les notions des différents chapitres de ce manuel sont regroupées dans un ensemble
d’activités : problèmes ouverts, problèmes de synthèse et QCM. Le but est de développer les compétences
utiles pour le bac : organiser ses connaissances, mener un raisonnement, rédiger clairement la résolution
d’un problème.
MATRICES ET SUITES
■ MS1 MATRICES : OPÉRATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
1. Définitions et vocabulaire
2. Opérations sur les matrices
3. Matrices inversibles
4. Résolution d’un système linéaire
■ MS2 SUITES DE MATRICES ET MARCHES ALÉATOIRES ...................................... 115
1. Puissances d’une matrice
2. Suites de matrices colonnes
3. Marche aléatoire
■ RABATS
Mémento AlgoBox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I
Le manuel numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II et III
Syntaxe de différents langages de programmation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV
Mémento d’algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V et VI
LOGOS ET INDICATIONS
19 Exercice corrigé en fin de manuel
Exercice avec l’ordinateur
Exercice avec la calculatrice
Exercice d’algorithmique
3
TRAVAILLER UN CHAPITRE manuel numérique , deux outils complémentaires
Manuel et
Auto-évaluation
Des ressources numériques pour préparer
le chapitre sur manuel.sesamath.net @ Chapitre AR3
Les nombres premiers
1 Montrer que les nombres suivants sont des 4 Traduire avec une seule égalité de congruence les
nombres premiers : propositions suivantes : Auto-évaluation
1) n est divisible par 6. 1 Ils ne comptent aucun diviseur autre que 1 et
1) 31 2) 47 3) 53 4) 61 5) 83
2) n est divisible par 3 et par 5. eux-même.
3) n est divisible par 4 et par 6.
2 Sans calculatrice, à l’aide des critères de divisibi- 2 1) divisible par 3 5) divisible par 11
4) n est divisible par 8 et par 9.
lité par 3, 5 et 11 ou de la division par 7, montrer que
2) divisible par 7 6) divisible par 7
les nombres suivants ne sont pas premiers :
5 Traduire par une phrase les propositions sui- 3) divisible par 11 7) divisible par 11
1) 57 3) 143 5) 341 7) 319 vantes sans utiliser le mot « congruence » : 4) divisible par 5 8) divisible par 3
2) 91 4) 265 6) 427 8) 1581 1) n ≡ 0 (5).
2) si n ≡ 0 (4) et n ≡ 0 (5), alors n ≡ 0 (20).
3 Sans calculatrice, donner tous les diviseurs des
3) Si n 25 et si n ≡ 0 (2), n ≡ 0 (3), n ≡ 0 (5)
nombres suivants :
alors n est premier.
1) 16 3) 24 5) 45 7) 63 4) Si p est premier et si ab ≡ 0 ( p), alors a ≡ 0 ( p) ou
2) 15 4) 36 6) 51 8) 91 b ≡ 0 ( p ).
Pour calculer la matrice C égale à AB, on vérifie que le nombre de colonnes de A est égal au
B
nombre de lignes de B, puis on dispose les matrices suivant le schéma de sorte que
2 Refaites les exercices corrigés A C
cij soit à l’intersection du prolongement de la i-ème ligne de A et de la j-ième colonne de B.
des méthodes du cours.
⎛ ⎞
2 1 −3
⎜ ⎟
1 3 5 −2 ⎜3 −1 0 ⎟
Exercice d’application Soit A = et B = ⎜
⎜0
⎟. Calculer AB.
−2 0 −3 2 ⎝ −2 2 ⎟⎠
2 −3 −4
Correction ⎛ ⎞
A est de taille 2 × 4 et B de taille 4 × 3. 2 1 −3
⎜ ⎟
A a autant de colonnes que B a de lignes, donc ⎜3 −1 0 ⎟
⎜ ⎟
C = AB existe et sa taille est 2 × 3. ⎜0 −2 2 ⎟
⎝ ⎠
On dispose les matrices comme ci-contre. 2 −3 −4
30 MÉTHODE 1 p. 90
3 Faites l’ exercice d’entraînement
Effectuer les produits des matrices suivantes :
lié à la méthode.
⎛ ⎞
4
⎛ ⎞
4
2 1 −1 ⎜ ⎟
⎜ ⎟
1) ⎝−1⎠ 3) ⎝1⎠ 2 −1 1
−3 1 0
4 Vérifiez vos réponses en fin de manuel 1 2
⎛ ⎞⎛ ⎞
−1 2 1 1
⎛ ⎞ 5 2 2 −1 ⎜ ⎟⎜ ⎟
8 −4 4 2) 4) ⎝ 0 2 2⎠ ⎝−2⎠
6 −1 2 −3 1
30 1) 3) ⎝2 −1 1⎠ −2 3 1 1
−13
4 −2 2
⎛ ⎞
−4
4 −3
2) 4) ⎝−2⎠
−8 3
−7
4 Travailler un chapitre
3 S’ENTRAÎNER POUR LE BAC
1 Repérez les éléments importants de la consigne , 28 Le graphe probabiliste suivant décrit la succession
des voyelles (V) et des consonnes (C) dans le roman
comme les verbes d’action à l’infinitif.
Eugène Onéguine de Pouchkine (voir 6 page 115) :
7/8
2 Vérifiez votre compréhension du vocabulaire.
1/8 V C 1/3
→ utilisez le lexique à la fin du manuel ou sur le
2/3
manuel numérique .
On note par une matrice ligne Pn la répartition de pro-
babilité à la n-ième lettre du livre.
3 Réalisez un schéma si nécessaire ou utilisez un 1) Déterminer la matrice de transition T telle que
tableur, une calculatrice, un logiciel de géométrie Pn+1 = Pn T.
dynamique… 2) Déterminer un réel λ et une matrice Q tels que :
Pn+1 = λPn + Q.
4 PRÉPARER LE BAC
54 Pour établir la liste des nombres premiers inférieurs à 4 000 à l’aide du crible d’Ératosthène, on raye les
multiples des nombres premiers jusqu’à :
a 61 b 67 c 100 d 4 000
3 Réalisez le QCM de fin de chapitre.
55 On considère le nombre N = n + (n + 2) + n(n + 2) avec n ∈ N. Le nombre N est premier :
a si n est impair. c pour les 4 premières valeurs impaires de n.
4 Vérifiez vos réponses en fin de manuel. b pour aucune valeur de n. d si n est premier.
5 Consultez les compléments proposés dans le 56 Parmi les phrases suivantes, quelles sont celles qui sont vraies ?
57 Parmi les phrases suivantes, quelles sont celles qui sont vraies ?
Travailler un chapitre 5
MÉTHODES DE L’ANNÉE
Arithmétique
Utiliser la divisibilité pour résoudre un problème............................................................. 10
Utiliser la définition de la division euclidienne ................................................................ 12
Déterminer un reste dans une division euclidienne .......................................................... 14
Démontrer qu’un nombre est divisible par un autre nombre .............................................. 15
Construire un tableau de congruence ............................................................................ 15
Calculer le PGCD de deux nombres ............................................................................... 32
Montrer que deux nombres sont premiers entre eux ........................................................ 34
Déterminer un couple (u ; v ) tel que au + bv = 1 .............................................................. 34
Résoudre une équation du type ax + by = c .................................................................... 37
Montrer qu’un nombre est premier ................................................................................ 55
Décomposer un nombre en produit de facteurs premiers ................................................. 58
Déterminer le PGCD de deux nombres à partir d’une décomposition en produit de
facteurs premiers .......................................................................................................... 59
Trouver le nombre de diviseurs d’un entier ..................................................................... 60
Déterminer un entier conditionné par ses diviseurs ......................................................... 61
Matrices
Multiplier deux matrices .............................................................................................. 90
Effectuer un calcul matriciel avec la calculatrice ............................................................. 91
Résoudre un système de deux équations à deux inconnues ............................................. 93
Résoudre un système linéaire avec la calculatrice ou un logiciel ...................................... 94
Déterminer M n lorsque M est diagonalisable ...............................................................121
Expliciter Un pour (Un ) définie par Un+1 = AUn + B .................................................122
Étudier le comportement asymptotique d’une marche aléatoire .......................................125
6 MÉTHODES DE L’ANNÉE
ARITHMÉTIQUE
Multiples.
Division euclidienne. 1
Congruence
Auto-évaluation
Des ressources numériques pour préparer
le chapitre sur manuel.sesamath.net @
1 Sans l’aide de la calculatrice, déterminer si les 6 On divise 7 entiers naturels successifs par 7.
nombres suivants sont divisibles par 4. Quels sont les restes obtenus ?
1) 136 3) 1 352 7 On donne : 117 = 6 × 17 + 15.
2) 514 4) 9 894 1) Dans la division de 117 par 17, donner le dividende,
7
Activités d’approche
1. Avant-propos
L’arithmétique a pour objet l’étude des nombres entiers.
Ces entiers peuvent être naturels (N = {0, 1, 2, 3, . . . }) ou relatifs (Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . . }).
« L’arithmétique [. . .] a le privilège d’avoir passionné les mathématiciens les plus éminents en même
temps qu’elle n’a cessé d’attirer les amateurs. Cette séduction tient, pour beaucoup, dans ce dernier
cas, au fait que des problèmes très difficiles, parfois non résolus, ont souvent des énoncés simples qui
peuvent être compris à partir d’une formation mathématique élémentaire. Gauss tenait l’arithmétique
pour la “la reine des mathématiques” et on a pu dire que la théorie des nombres était “la plus pure des
mathématiques pures”. »
François Le Lionnais (1901-1984), dans Dictionnaire des mathématiques, Éditions Puf, 1979
PROPRIÉTÉS
Principe du bon ordre : toute partie non vide de N admet un plus petit élément.
Principe de descente infinie : toute suite dans N strictement décroissante est stationnaire
à partir d’un certain rang.
Principe des tiroirs : si on range (n + 1) chaussettes dans n tiroirs, alors au moins un tiroir
contiendra au moins 2 chaussettes.
Les deux premières propriétés seront utilisées dans les deux prochains chapitres.
Lorsqu’on s’intéresse à la partie décimale du résultat de la division d’un entier par n, on est sûr qu’à partir de la
(n + 1)-ième décimale, on obtiendra un reste déjà obtenu (principe des tiroirs). Cela explique la partie décimale
périodique d’un nombre rationnel non décimal.
R EMARQUES :
D’autres formulations sont possibles : « a est divisible par b », « b divise a », « b est un
diviseur de a » pour décrire la relation a = kb.
On utilise aussi la notation b | a pour signifier que b divise a.
Exemples
1) 6 = 2 × 3 donc 2 et 3 sont des diviseurs de 6.
Les diviseurs dans N de 6 sont : 1, 2, 3, 6.
2) −52 = (−4) × 13 donc −4, 4, −13 et 13 sont des diviseurs de −52.
Les diviseurs dans Z de −52 sont : −52, −26, −13, −4, −2, −1, 1, 2, 4, 13, 26, 52.
PROPRIÉTÉS
Exercice d’application Déterminer tous les couples d’entiers naturels ( x; y) tels que :
x2 − 2xy = 15.
Exercice d’application Déterminer tous les entiers relatifs n tels que ( n − 3) divise ( n + 5).
PROPRIÉTÉ
PREUVE On sait que a divise b et c, donc il existe deux entiers relatifs k et k′ tels que :
b = ka et c = k′ a.
Donc d doit diviser 5. Comme 5 n’a que deux diviseurs positifs 1 et 5, les diviseurs positifs
communs à a et b sont à chercher dans {1 ; 5}.
3. La division euclidienne
DÉFINITION ET THÉORÈME
Soit a un entier relatif et b un entier naturel non nul.
On appelle division euclidienne de a par b, l’opération qui, au couple ( a ; b ), associe l’unique
couple (q ; r ) tel que :
a = bq + r avec 0 6 r < b.
a s’appelle le dividende, b le diviseur, q le quotient et r le reste.
Exemples
1) La division euclidienne de 114 par 8 correspond à : 114 = 8 × 14 + 2.
Ainsi q = 14 et r = 2.
2) Pour avoir un reste positif dans la division euclidienne de −114 par 8, on écrit : −2 = 6 − 8.
On obtient alors : −114 = 8 × (−14) − 2 = 8 × (−14) − 8 + 6 = 8 × (−15) + 6.
Ainsi q = −15 et r = 6.
R EMARQUES :
Le reste est toujours un entier naturel inférieur au diviseur. Par conséquent, dans la divi-
sion par 7, par exemple, il existe 7 restes possibles : 0, 1, 2, 3, 4, 5, 6.
a b
On peut schématiser la division euclidienne comme on pose une division :
r q
114 8
Ainsi, en reprenant l’exemple de la division de 114 par 8, on a :
2 14
Exercice d’application Trouver tous les entiers dont le quotient dans la division euclidienne par
5 donne un quotient égal à 3 fois le reste.
Correction Soit a un entier qui vérifie la condition de l’énoncé. On divise a par 5, on a alors :
a = 5q + r avec 0 6 r < 5.
Comme q = 3r, on a : a = 15r + r = 16r avec 0 6 r < 5.
Exercice d’application Lorsqu’on divise a par b, le reste est 8 et lorsqu’on divise 2a par b, le reste
est 5. Déterminer le diviseur b.
Correction Écrivons chacune des deux divisions euclidiennes, en notant q et q ′ les quotients
respectifs :
a = bq + 8 avec b>8
2a = bq ′ + 5 avec b>5
b est donc un multiple positif non nul de 11, supérieur à 8, donc : b = 11.
4. Congruence
A. Entiers congrus à n
DÉFINITION
Soit n un entier naturel (n > 2), a et b deux entiers relatifs.
On dit que deux entiers a et b sont congrus modulo n si, et seulement si, a et b ont le même
reste dans la division euclidienne par n. On note alors :
Exemples
1) 57 ≡ 15 (7) car : 57 = 7 × 8 + 1 et 15 = 7 × 2 + 1
41 ≡ −4 (9) car : 41 = 9 × 4 + 5 et − 4 = 9 × (−1) + 5
2) Un nombre est congru à son reste modulo n dans la division euclidienne par n.
2 008 ≡ 8 (10) car 2 008 = 10 × 200 + 8 ; 17 ≡ 1 (4) ; 75 ≡ 3 (9).
3) Si x ≡ 0 (2), alors x est pair.
Si x ≡ 1 (2), x est impair.
PROPRIÉTÉS
a ≡ 0 (n) ⇔ a est un multiple de n ou n est un diviseur de a.
La congruence est une relation d’équivalence, c’est-à-dire, pour tous entiers a, b, c, on a :
1) a ≡ a (n) (réflexivité)
2) Si a ≡ b (n), alors b ≡ a (n) (symétrie)
3) Si a ≡ b (n) et si b ≡ c (n), alors a ≡ c (n) (transitivité)
THÉORÈME
Soit n un entier naturel (n > 2), a et b deux entiers relatifs.
a ≡ b (n) ⇔ a − b ≡ 0 (n)
PREUVE Comme il s’agit d’une équivalence, il faut démontrer la propriété dans les deux
sens.
• Dans le sens direct : On sait que a ≡ b (n). Il existe donc des entiers q, q ′ et r tels que :
a = nq + r et b = nq ′ + r avec 0 6 r < n.
On obtient : a − b = n(q − q ′ ).
a−b est alors un multiple de n, et son reste dans la division par n est nul, d’où : a − b ≡ 0 (n).
a ≡ b (n) et c ≡ d ( n ).
PREUVE
1) Compatibilité avec l’addition
On sait que : a ≡ b (n) et c ≡ d (n), donc ( a − b ) et (c − d) sont des multiples de n.
Il existe donc deux entiers relatifs k et k′ tels que : a − b = kn et c − d = k′ n.
En additionnant ces deux égalités, on obtient :
a − b + c − d = kn + k′ n ⇔ ( a + c) − (b + d) = (k + k′ )n.
Exercice d’application Déterminer les restes dans la division euclidienne par 7 des nombres :
Correction
1) On a 50 ≡ 1 (7) car 50 = 7 × 7 + 1.
D’après la compatibilité avec les puissances, on a : 50100 ≡ 1100 ≡ 1 (7).
Le reste est 1.
R EMARQUE : La notion de congruence prend ici tout son intérêt. Par exemple, bien que l’on
ne puisse calculer 50100 + 100100 , on peut connaître son reste dans la division par 7 de façon
simple et rapide.
MÉTHODE 4 Démontrer qu’un nombre est divisible par un autre nombre Ex. 29 p. 17
Exercice d’application Montrer que : ∀n ∈ N, 3n+3 − 44n+2 est divisible par 11.
Correction On a : 3n+3 = 3n × 33 = 27 × 3n .
Or 27 ≡ 5 (11), donc d’après la compatibilité avec la multiplication, on a :
∀n ∈ N, 3n+3 ≡ 5 × 3n (11)
n
On a : 44n+2 = 44 × 42 , or 42 ≡ 5 (11) donc 44 ≡ 52 ≡ 3 (11), donc :
∀n ∈ N, 44n+2 ≡ 3n × 5 (11)
Exercice d’application
Correction
1) On détermine les restes suivant une méthode exhaustive, c’est-à-dire on détermine les restes
de n2 à partir de chaque reste possible de la division de n par 7.
On peut construire un tableau de congruence pour présenter les résultats :
Reste de la division
0 1 2 3 4 5 6
de n par 7
Reste de la division
0 1 4 2 2 4 1
de n2 par 7
40 D’après Bac (Antilles Guyane - 2011) de naissance et multipliez-le par 37. Ajoutez les deux
On considère l’équation (F) : 11x2 − 7y2 = 5, où x et y nombres obtenus. Je pourrai alors vous donner la date
sont des entiers relatifs. de votre anniversaire »
1) Démontrer que si le couple ( x ; y) est solution de (F), Un spectateur annonce 308 et en quelques secondes,
alors x2
≡ 2y2(mod 5). le magicien déclare : « Votre anniversaire tombe le 1er
2) Soient x et y des entiers relatifs. Recopier et complé- août ! ».
ter les deux tableaux suivants :
Modulo 5, x est congru à 0 1 2 3 4 1) Vérifier que pour une personne née le 1er août, le pro-
Modulo 5, x2 est congru à gramme de calcul (A) donne effectivement le nombre
308.
Modulo 5, y est congru à 0 1 2 3 4 2) a) Pour un spectateur donné, on note z le résultat ob-
Modulo 5, 2y2 est congru à tenu en appliquant le programme de calcul (A).
Exprimer z en fonction de j et de m et démontrer
Quelles sont les valeurs possibles du reste de la divi-
que z ≡ m (12).
sion euclidienne de x2 et de 2y2 par 5 ?
b) Retrouver alors la date de l’anniversaire d’un
3) En déduire que si le couple ( x ; y) est solution de (F),
spectateur ayant obtenu le nombre 455 en appli-
alors x et y sont des multiples de 5.
quant le programme de calcul (A).
41 D’après Bac (Nouvelle-Calédonie - 2009)
On considère l’équation notée (G) :
3x2 + 7y2 = 102n où x et y sont des entiers relatifs. PARTIE B
1) Montrer que 100 ≡ 2 (modulo 7). Lors d’une autre représentation, le magicien décide de
Démontrer que si ( x ; y) est solution de (G) alors changer son programme de calcul. Pour un spectateur
3x2 ≡ 2n (modulo 7). dont le numéro du jour de naissance est j et le numéro
2) Reproduire et compléter le tableau suivant : du mois de naissance est m, le magicien demande de
Reste de la division calculer le nombre z défini par z = 12j + 31m.
0 1 2 3 4 5 6
de x par 7 On considère l’algorithme ci-dessous :
Reste de la division
de 3x2 par 7. 1. Liste des variables utilisées
2. j, m, z : entiers
3) Démontrer que 2n est congru à 1, 2 ou 4 modulo 7.
3. Traitement et affichage
En déduire que l’équation (G) n’admet pas de
4. Pour m variant de ... à ... faire
solution.
5. Pour j variant de ... à ... faire
42 D’après Bac (Polynésie - 2014) ALGO 6. Donner à z la valeur de 12j + 31m
Dans cet exercice, on appelle numéro du jour de nais- 7. Si ... Alors
sance j le rang de ce jour dans le mois et numéro du 8. Afficher la valeur de j, m
mois de naissance m, le rang du mois dans l’année. 9. Fin Si
Par exemple, pour une personne née le 14 mai, alors 10. Fin Pour
j = 14 et m = 5. 11. Fin Pour
PARTIE A
Lors d’une représentation, un magicien demande aux 1) Compléter cet algorithme afin qu’il affiche toutes les
spectateurs d’effectuer le programme de calcul (A) valeurs de j et de m telles que :
suivant : 12j + 31m = 503.
« Prenez le numéro de votre jour de naissance et 2) Quelle est alors la date d’anniversaire correspon-
multipliez-le par 12. Prenez le numéro de votre mois dante ?
58 Il existe un entier k pour lequel 9k + 2 et 7k + 3 ont pour diviseur commun d tel que :
a d = 13 b d=2 c d=3 d d=6
TP 2 Division euclidienne
Pour faire comprendre la division d’un entier naturel par un entier naturel non nul à l’école
primaire, on procède par soustractions successives, c’est-à-dire que, si l’on veut diviser 32
par 5, on soustrait 5 à 32 autant de fois que cela est possible.
32 − 5 = 27
27 − 5 = 22
22 − 5 = 17
17 − 5 = 12
12 − 5 = 7
7−5 = 2
TP 3 Notion de base
Notre système de numération est un système décimal de position. Il est constitué de 10 chiffres
dont la position indique le nombre d’unités de la puissance de 10 correspondante.
a) En prenant exemple sur la conversion de 496 dans le base 7, convertir le nombre 2 016
dans la base 2.
b) Convertir, par la même méthode, le nombre 68 425 dans la base 8.
c) Convertir, par la même méthode, le nombre 2 278 dans la base 12.
d) Démontrer que les divisions euclidiennes successives d’un nombre N, puis des quotients
par la base b finissent par s’arrêter à partir d’un certain rang n.
Exprimer alors le nombre N dans la base b à l’aide des restes successifs r1 , r2 , . . ., rn .
3) Q représente l’écriture d’un nombre en base B et N l’écriture décimale.
a) Conversion dans le système décimal
Soit l’algorithme suivant :
b) Conversion en base B.
Soit l’algorithme suivant :
Récréation, énigmes
Jeu de Nim
On a disposé 40 allumettes sur un tapis.
Deux joueurs prennent chacun, à tour de rôle, une, deux trois ou quatre
allumettes. Celui qui prend la dernière allumettes perd la partie.
Il existe une stratégie gagnante pour le joueur qui commence.
Exposer cette stratégie. Généraliser ensuite à un nombre n d’allumettes.
PGCD. Théorèmes de 2
Bézout et de Gauss
Auto-évaluation
Des ressources numériques pour préparer
le chapitre sur manuel.sesamath.net @
1 « PGCD » signifie : « plus grand commun 2) Un nombre entier a est divisible par 8 et 9, donc a
diviseur ». est divisible par 72.
26
1) Calculer le PGCD de 26 et 65, puis simplifier . 3) Un nombre entier a est divisible par 4 et 18, donc
65
72 a ≡ 36 (36).
2) Calculer le PGCD de 72 et 54, puis simplifier . 4) Un nombre entier a est divisible par 10 et 15, donc
54
255 a ≡ 0 (150).
3) Calculer le PGCD de 255 et 35, puis simplifier .
35 5 Soit x et y des nombres entiers. Les phrases sui-
2 Soit n un entier naturel. Le PGCD de n et de 72
vantes sont-elles vraies ou fausses ? Justifier.
vaut 8. Parmi les valeurs suivantes quelles sont celles 1) Si x ≡ 0 (81), alors x ≡ 0 (9).
que peut prendre n ? 2) L’équation x2 + 2y2 ≡ 3 (4) admet des solutions.
9, 16, 18, 24, 32, 40, 48
6 Trouver un couple d’entiers ( x ; y) vérifiant les
3 Deux nombres sont premiers entre eux si leur
équations suivantes :
PGCD est égal à 1.
1) 7x − 10y = 1 3) 3x + 4y = 3
1) 9 et 16 sont-ils premiers entre eux ?
2) 4x + 5y = 1 4) 7x − 12y = 3
2) 35 et 91 sont-ils premiers entre eux ?
3) 31 et 67 sont-ils premiers entre eux ? 7 Pierre a des jetons d’une valeur de 3 points et
4 Les phrases suivantes sont-elles vraies ou Jean a des jetons d’une valeur de 7 points.
fausses ? Justifier. Pierre doit donner 34 points à Jean.
1) Un nombre entier a est divisible par 6 et 9, donc a Comment Pierre et Jean peuvent-il procéder ? Donner
est divisible par 54. une solution.
27
Activités d’approche
2) Dans cette question, le volume de la boîte B est v = 77 760. On sait que, pour remplir la
boîte B, la plus grande valeur possible de a est 12.
On pose : ℓ = aℓ′ et L = aL′ .
a) Que peut-on dire de PGCD(ℓ′ ; L′ ) si a = 12 ? Pourquoi ?
b) Vérifier, dans le cas a = 12, que ℓ′2 L′ = 45.
c) Montrer qu’il y a exactement deux boîtes B possibles dont on donnera les dimensions.
1) Pourquoi peut-on trouver un entier naturel x0 > 0 tel que le couple ( x0 ; y0 ) soit solution
de (E) ?
Exemple : Si l’on veut coder la lettre G par la fonction f ( x ) = 11x + 8, on passe par les étapes
suivantes : G ⇒ x = 6 ⇒ 11 × 6 + 8 = 74 ⇒ 74 ≡ 22 (26) ⇒ y = 22 ⇒ W
La lettre G est donc codée par la lettre W.
1) Coder la lettre W.
2) Existence d’une fonction de décodage.
Théorème de Bézout : a et b sont deux entiers naturels. « a et b sont premiers entre eux »
équivaut à « il existe deux entiers relatifs u et v tels que au + bv = 1 ».
a) Pourquoi le théorème de Bézout permet-il d’affirmer qu’il existe un entier relatif u tel
que : 11u + 26v = 1 ?
b) Montrer alors que l’équation 11x ≡ 1 (26), puis que l’équation 11x ≡ j (26), j étant un
entier naturel, admettent une solution.
Par une étude statistique de la fréquence d’apparition des lettres sur un passage plus impor-
tant, on déduit que le chiffrement est affine, que la lettre E est codée par la lettre E et que la
lettre J est codée par la lettre N.
Soit la fonction affine f définie par : f ( x ) = ax + b où a et b sont des entiers naturels compris
entre 0 et 25.
4a + b ≡ 4 (26)
1) Démontrer que a et b vérifient le système suivant :
9a + b ≡ 13 (26)
PREUVE Existence
L’ensemble des diviseurs communs à a et b est un ensemble fini car c’est l’intersection de deux
ensembles finis.
De plus, 1 divise a et b donc l’ensemble des diviseurs communs à a et b est non vide.
Or tout ensemble fini non vide dans Z admet un plus grand et unique élément, donc d existe.
PROPRIÉTÉ
PGCD( a, b ) = PGCD(b, a)
PGCD( a, b ) = PGCD(| a|, |b |)
PGCD( a, 0) = a car 0 est multiple de tout entier.
Si b divise a, alors PGCD( a, b ) = |b |.
Pour tout entier naturel k non nul, on a : PGCD(ka, kb ) = k PGCD( a, b ).
Exemples
• PGCD(82, 0) = 82.
• PGCD(−24, −18) = PGCD(24, 18) = 6.
• PGCD(30, 5) = 5 car 30 est un multiple de 5.
• PGCD(240, 180) = 10PGCD(24, 18) = 60.
Exemples
• PGCD(15, 8) = 1 donc 15 et 8 sont premiers entre eux.
• PGCD( a, 1) = 1. Le nombre 1 est premier avec tout entier.
ATTENTION : Il ne faut pas confondre des nombres premiers entre eux et des nombres
premiers. 15 et 8 ne sont pas premiers et pourtant ils sont premiers entre eux.
Par contre, deux nombres premiers distincts sont nécessairement premiers entre eux.
C. Algorithme d’Euclide
THÉORÈME
Soit a et b deux entiers naturels non nuls tels que b ne divise pas a.
La suite des divisions euclidiennes suivantes finit par s’arrêter. Le dernier reste non nul est
alors le PGCD de a et de b.
Division de a par b a = b q0 + r0 avec b > r0 > 0
Division de b par r0 b = r0 q1 + r1 avec r0 > r1 > 0
Division de r0 par r1 r0 = r1 q2 + r2 avec r1 > r2 > 0
.. ..
. .
Division de rn−2 par rn−1 r n−2 = r n−1 q n + r n avec rn−1 > rn > 0
Division de rn−1 par rn r n−1 = r n q n+1 + 0
On a alors PGCD( a, b ) = rn .
PREUVE
• Montrons que PGCD( a, b ) = PGCD(b, r0 ).
• La suite des restes : r0 , r1 , r2 , . . ., rn est une suite strictement décroissante dans N car :
r0 > r1 > r2 > · · · > r n .
D’après le principe de descente infinie, il existe alors n tel que rn+1 = 0.
R EMARQUE : Le petit nombre d’étapes de cet exemple montre la performance de cet algo-
rithme à comparer avec la décomposition en facteurs premiers (voir chapitre A3).
ALGO Voir TP 1 pour la performance de l’algorithme.
2. Théorème de Bézout
Sur la pierre tombale d’Étienne Bézout (né à Nemours, le 31 mars
1730 et mort aux Basses-Loges, le 27 septembre 1783), dans l’église
Saint-Pierre à Avon (en Seine-et-Marne), on peut lire cette épitaphe :
A. Identité de Bézout
PROPRIÉTÉ
Soit a et b deux entiers non nuls et D = PGCD( a, b ).
Il existe alors un couple (u, v) d’entiers relatifs telle que : au + bv = D.
PREUVE
Soit G l’ensemble formé par les entiers naturels strictement positifs de la forme ma + nb où m
et n sont des entiers relatifs.
G est une partie de N non vide : on vérifie facilement que | a| ∈ G.
D’après le principe du bon ordre, G admet donc un plus petit élément d tel que d = au + bv.
• D = PGCD( a, b ) divise a et b donc D divise au + bv = d et donc D 6 d.
d divise a et b, donc d 6 D.
• Conclusion : D 6 d et d 6 D donc D = d.
B. Théorème de Bézout
THÉORÈME
Deux entiers relatifs a et b sont premiers entre eux si, et seulement si, il existe deux entiers
relatifs u et v tels que :
au + bv = 1
MÉTHODE 2 Montrer que deux nombres sont premiers entre eux Ex. 22 p. 39
Exercice d’application
Correction Il faut prouver qu’il existe des coefficients u et v tels que u (2n + 1) + v(3n + 2) = 1.
Exercice d’application
Montrer que 59 et 27 sont premiers entre eux, puis déterminer un couple d’entiers relatifs ( x, y)
tel que : 59x + 27y = 1.
Correction
Pour montrer que 59 et 27 sont premiers entre Pour déterminer un couple ( x ; y), on remonte
eux, on effectue l’algorithme d’Euclide. l’algorithme d’Euclide :
59 = 27 × 2 + 5 ( 1) de (3) on obtient :
27 = 5 × 5 + 2 ( 2) 2×2 = 5−1
On multiplie l’égalité (2) par 2
5 = 2×2+1 ( 3)
27 × 2 = 5 × 10 + 2 × 2
Le dernier reste est 1. Donc PGCD(59, 27) = 1
27 × 2 = 5 × 10 + 5 − 1
et 59 et 27 sont premiers entre eux.
27 × 2 = 5 × 11 − 1
5 × 11 = 27 × 2 + 1
On multiplie l’égalité (1) par 11
59 × 11 = 27 × 22 + 5 × 11
59 × 11 = 27 × 22 + 27 × 2 + 1
59 × 11 = 27 × 24 + 1
On a donc :
59 × 11 + 27 × (−24) = 1
C. Corollaire de Bézout
PROPRIÉTÉ
L’équation ax + by = c admet des solutions entières si, et seulement si, c est un multiple du
PGCD( a, b ).
PREUVE
• Dans le sens direct : Supposons que l’équation ax + by = c admette une solution ( x0 ; y0 ).
Soit D = PGCD( a, b ) alors, comme D divise a et b, il divise ax0 + by0 .
D divise donc c.
Exemple
• L’équation 4x + 9y = 2 admet des solutions car PGCD(4, 9) = 1 et 2 est multiple de 1.
En effet, si x = −4 et y = 2, on a : 4(−4) + 9(2) = −16 + 18 = 2.
• L’équation 9x − 15y = 2 n’admet pas de solution car PGCD(9, 15) = 3 et 2 n’est pas
multiple de 3.
THÉORÈME
PREUVE Si a divise le produit bc, alors il existe un entier k tel que : bc = ka.
Si a et b sont premiers entre eux, d’après le théorème de Bézout, il existe deux entiers u et v tels
que : au + bv = 1.
En multipliant par c, on a :
acu + bcv = c or bc = ka, donc :
acu + kav = c
a(cu + kv) = c
Donc a divise c.
Exemple Pour trouver les solutions dans Z2 de l’équation 5( x − 1) = 7y, on sait que :
B. Corollaire de Gauss
PROPRIÉTÉ
Si b et c divisent a et si b et c sont premiers entre eux, alors bc divise a.
a = kb et a = k′ c donc : kb = k′ c.
a = k′ c = k′′ bc
Donc bc divise a.
4. Équation diophantienne ax + by = c
A. Définition et existence
DÉFINITION
Une équation diophantienne est une équation à coefficients entiers dont on cherche les so-
lutions entières. Soit a, b et c trois entiers relatifs, les équations diophantiennes du premier
degré sont du type : ax + by = c.
R EMARQUE : Diophante d’Alexandrie est un mathématicien grec du IIIe siècle de notre ère.
PROPRIÉTÉ
Une équation diophantienne du premier degré, de la forme ax + by = c, où a, b et c sont des
entiers relatifs, admet des solutions si, et seulement si, c est un multiple du PGCD( a, b ).
Exemple L’équation 17x − 33y = 1 admet des solutions car PGCD(17, 33) = 1.
B. Résolution
MÉTHODE 4 Résoudre une équation du type ax + by = c Ex. 42 p. 40
Exercice d’application Déterminer l’ensemble des solutions de l’équation (E) 17x − 33y = 1.
Correction
1) On cherche une solution particulière de (E). Ici, il existe une solution évidente : le couple
(2 ;1), car 17 × 2 − 33 × 1 = 34 − 33 = 1.
17x − 33y = 1
2) On recherche ensuite la solution générale de (E). On a : .
17 × 2 − 33 × 1 = 1
Par soustraction termes à termes des deux égalités, on obtient :
33 divise 17( x − 2). Or PGCD(17, 33) = 1, donc d’après le théorème de Gauss, 33 divise
( x − 2). On a donc : x − 2 = 33 k, k ∈ Z. En remplaçant dans (E’), on trouve y − 1 = 17 k.
x = 2 + 33 k
3) Les solutions de (E) sont de la forme : , k ∈ Z.
y = 1 + 17 k
Correction
1) L’équation (E1 ) admet des solutions car 15 et 8 sont premiers entre eux.
2) On cherche une solution particulière à l’équation (E2 ) : 15x + 8y = 1.
(−1 ; 2) est solution évidente à (E2 ) car : 15 × (−1) + 8 × 2 = −15 + 16 = 1.
3) En multipliant par 5, on trouve alors une solution particulière à (E1 ). Le couple (−5 ; 10) est
solution de (E1 ).
15x + 8y = 5
4) On recherche ensuite la solution générale de (E1 ). On a : .
15(−5) + 8(10) = 5
Par soustraction termes à termes des deux égalités on obtient :
15( x + 5) + 8(y − 10) = 0 ⇔ 15( x + 5) = 8(10 − y) (E2 )
8 divise 15( x + 5). Or PGCD(15, 8) = 1, donc d’après le théorème de Gauss, 8 divise ( x + 5).
On a donc : x + 5 = 8 k, k ∈ Z.
En remplaçant dans l’équation (E2 ), on trouve 10 − y = 15 k.
x = −5 + 8 k
5) Les solutions de (E1 ) sont de la forme : , k ∈ Z.
y = 10 − 15 k
1 Déterminer de tête et à l’aide des règles de divisi- 9 Dresser la liste des diviseurs positifs de 72 et de
bilité, les PGCD des entiers suivants : 60. En déduire leur PGCD.
32 Vrai ou faux ?
21 Soit l’égalité de Bézout : « Soit a et b deux entiers
S’il existe deux entiers relatifs u et v tel que au + bv = 3,
non nuls et D leur PGCD. Il existe un couple d’entiers
alors le PGCD de a et de b est égal à 3. Justifier.
relatifs telle que au + bv = D ».
1) Démontrer le théorème de Bézout « a et b sont pre- 33 Résoudre dans N2 les systèmes suivants.
miers entre eux si, et seulement si, il existe un couple
On donnera la réponse sous forme d’un tableau.
d’entiers relatifs (u; v) tel que au + bv = 1 ».
2) En déduire que si PGCD( a; b ) = D, alors a = Da′ et xy = 1512 xy = 300
1) 2)
b = Db ′ avec PGCD( a′ ; b ′ ) = 1. PGCD( x, y) = 6 PGCD( x, y) = 5
En montagne, un randonneur a effectué des réserva- PARTIE A : Restitution organisée des connaissances
tions dans deux types de gîte : l’hébergement A et l’hé- On rappelle ci-dessous le théorème de Bézout et le théo-
bergement B. rème de Gauss.
Théorème de Bézout :
Une nuit en hébergement A coûte 24 e et une nuit en
« Deux entiers relatifs a et b sont premiers entre eux si et
hébergement B coûte 45 e.
seulement si, il existe un couple (u, v) d’entiers relatifs
Il se rappelle que le coût total de sa réservation est de vérifiant au + bv = 1. »
438 e. Théorème de Gauss :
« Soient a, b, c des entiers relatifs. Si a divise le produit
bc et si a et b sont premiers entre eux, alors a divise c. »
On souhaite retrouver les nombres x et y de nuitées pas-
sées respectivement en hébergement A et en héberge-
1) En utilisant le théorème de Bézout, démontrer le
ment B.
théorème de Gauss.
1) a) Montrer que les nombres x et y sont respective- 2) Soient p et q deux entiers naturels tels que p et q sont
ment inférieurs ou égaux à 18 et 9. premiers entre eux.
b) Recopier et compléter les pointillés de l’algo- Déduire du théorème de Gauss que, si a est un entier
rithme suivant afin qu’il affiche les couples (x ; y) relatif, tel que a ≡ 0 ( p) et a ≡ 0 (q ), alors a ≡ 0 ( pq ).
possibles.
PARTIE B
1. Liste des variables utilisées
On se propose de déterminer l’ensemble S des entiers
2. x, y : entiers
relatifs n vérifiant le système :
3. Traitements et affichage
4. Pour x variant de 0 à ... faire n ≡ 9 (17)
5. Pour y variant de 0 à ... faire n ≡ 3 ( 5)
6. Si ... Alors
7. Afficher la valeur de x, y 1) Recherche d’un élément de S .
8. Fin Si On désigne par (u ; v) un couple d’entiers relatifs tel
9. Fin Pour que 17u + 5v = 1.
10. Fin Pour a) Justifier l’existence d’un tel couple (u ; v).
b) On pose n0 = 3 × 17u + 9 × 5v.
2) Justifier que le coût total de la réservation est un mul- Démontrer que n0 appartient à S .
tiple de 3. c) Donner un exemple d’entier n0 appartenant à S .
3) a) Justifier que l’équation 8x + 15y = 1 admet pour 2) Caractérisation des éléments de S .
solution au moins un couple d’entiers relatifs. a) Soit n un entier relatif appartenant à S .
b) Déterminer une telle solution. Démontrer que n − n0 ≡ 0 (85).
c) Résoudre l’équation (E) : 8x + 15y = 146 où x et y b) En déduire qu’un entier relatif n appartient à S
sont des nombres entiers relatifs. si, et seulement si, n peut s’écrire sous 1a forme
4) Le randonneur se souvient avoir passé au maximum n = 43 + 85k où k est un entier relatif.
13 nuits en hébergement A. 3) Application
Montrer alors qu’il peut retrouver le nombre exact Zoé sait qu’elle a entre 300 et 400 jetons. Si elle fait
de nuits passées en hébergement A et celui des nuits des tas de 17 jetons, il lui en reste 9.
passées en hébergement B. Si elle fait des tas de 5 jetons, il lui en reste 3.
Calculer ces nombres. Combien a-t-elle de jetons ?
50 D’après Bac (Nouvelle-Calédonie - 2007) 2) Cet algorithme donne en sortie le PGCD des entiers
naturels non nuls a et b.
1) Dans cette question x et y désignent des entiers rela- Le modifier pour qu’il indique si deux entiers natu-
tifs. rels non nuls a et b sont premiers entre eux ou non.
a) Montrer que l’équation ( E) : 65x − 40y = 1 n’a
pas de solution. PARTIE B
b) Montrer que l’équation ( E′ ) : 17x − 40y = 1 À chaque lettre de l’alphabet on associe grâce au ta-
admet au moins une solution. bleau ci-dessous un nombre entier compris entre 0 et 25.
c) Déterminer à l’aide de l’algorithme d’Euclide un
couple d’entiers relatifs solution de l’équation A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
( E ′ ).
N O P Q R S T U V W X Y Z
d) Résoudre l’équation ( E′ ).
13 14 15 16 17 18 19 20 21 22 23 24 25
En déduire qu’il existe un unique naturel x0 < 40
tel que : 17x0 ≡ 1 (40). On définit un procédé de codage de la façon suivante :
2) Pour tout naturel a, démontrer que si a17 ≡ b (55) Étape 1 : on choisit deux entiers naturels p et q compris
et si a40 ≡ 1 (55), alors b33 ≡ a (55). entre 0 et 25.
Étape 2 : à la lettre que l’on veut coder, on associe l’en-
51 D’après Bac (Antilles-Guyane - 2015) tier x correspondant dans le tableau ci-dessus.
PARTIE A Étape 3 : on calcule l’entier x ′ défini par les relations
Pour deux entiers naturels non nuls a et b, on note
x ′ ≡ px + q (26) et 0 6 x ′ 6 25.
r ( a, b ) le reste dans la division euclidienne de a par b.
On considère l’algorithme suivant :
Étape 4 : à l’entier x ′ , on associe la lettre correspondante
1. Liste des variables utilisées dans le tableau.
2. c : entier naturel
3. a, b : entiers naturels non nuls 1) Dans cette question, on choisit p = 9 et q = 2.
4. Entrées a) Démontrer que la lettre V est codée par la lettre J.
5. Saisir a b) Citer le théorème qui permet d’affirmer l’exis-
6. Saisir b tence de deux entiers relatifs u et v tels que :
7. Traitements 9u + 26v = 1. Donner sans justifier un couple
8. Donner à c la valeur de r ( a, b ) (u ; v) qui convient.
9. Tant que (c 6= 0) faire c) Démontrer que x ′ ≡ 9x + 2 (26) équivaut à :
10. Donner à a la valeur de b x ≡ 3x ′ + 20 (26).
11. Donner à b la valeur de c d) Décoder la lettre R.
12. Donner à c la valeur de r ( a, b ) 2) Dans cette question, on choisit q = 2 et p est inconnu.
13. Fin Tant que On sait que J est codé par D.
14. Affichage Déterminer la valeur de p (on admettra que p est
15. Afficher la valeur de b unique).
3) Dans cette question, on choisit p = 13 et q = 2.
1) Faire fonctionner cet algorithme avec a = 26 et b = 9 Coder les lettres B et D.
en indiquant les valeurs de a, b et c à chaque étape. Que peut-on dire de ce codage ?
Pour carreler une pièce rectangulaire mesurant 4,18 m Le but est de déterminer l’ensemble S des entiers rela-
sur 5,67 m, un carreleur propose à des propriétaires le tifs n vérifiant le système :
choix entre deux modèles de dalles carrées.
n ≡ 13 [19]
1) Le premier modèle a 29 cm de côté et coûte 2,30 e n ≡ 6 [12]
l’unité.
Avec ce modèle, il n’utilise que des dalles entières et
1) Recherche d’un élément de S .
il complète avec du joint autour de chaque dalle.
On désigne par (u ; v) un couple d’entiers relatifs tel
a) Calculer le nombre maximal de dalles que l’on
que 19u + 12v = 1.
peut poser dans la largeur de la pièce.
a) Justifier l’existence d’un tel couple (u ; v).
b) Calculer le nombre maximal de dalles que l’on
b) On pose n0 = 6 × 19u + 13 × 12v.
peut poser dans la longueur de la pièce.
Démontrer que n0 appartient à S .
c) Les joints autour des dalles auront-ils tous la
c) Donner un exemple d’entier n0 appartenant à S .
même largeur ?
2) Caractérisation des éléments de S .
Si oui, quelle est cette largeur ?
a) Soit n un entier relatif appartenant à S .
2) Le second modèle a 36 cm de côté et coûte 3,10 e
Démontrer que n − n0 ≡ 0 (228).
l’unité.
b) En déduire qu’un entier relatif n appartient à S
Avec ce modèle-là, il est préconisé d’utiliser des
si, et seulement si, n peut s’écrire sous la forme
joints de 0,6 cm et le carreleur est alors dans l’obliga-
n = −6 + 228k où k est un entier relatif.
tion de couper des dalles. Les découpes ne sont pas
3) Application.
réutilisées. Calculer le nombre de dalles nécessaires.
La comète A passe tous les 19 ans et apparaîtra la
3) Quel sera le choix le moins coûteux pour l’achat des
prochaine fois dans 13 ans.
dalles ?
La comète B passe tous les 12 ans et apparaîtra la pro-
chaine fois dans 6 ans.
53 Vrai ou faux ?
Dans combien d’années pourra-t-on observer les
Pour chacune des quatre propositions, indiquer si elle deux comètes la même année ?
est vraie ou fausse, et donner une démonstration de la
réponse choisie.
55 Restes chinois
1) Proposition 1 : ∀ n ∈ N ∗ , 3n et 2n + 1 sont premiers On se propose de résoudre dans Z le système :
entre eux.
2) On appelle S l’ensemble des couples ( x; y) d’entiers N ≡ 5 [13]
relatifs solutions de l’équation 3x − 5y = 2. N ≡ 1 [17]
Proposition 2 : « L’ensemble S est l’ensemble des
couples (5k−1 ; 3k−1) où k est un entier relatif. » 1) Vérifier que 239 est solution de ce système.
3) Soit a et b deux entiers naturels. 2) Soit N un entier relatif solution de ce système.
Proposition 3 : « S’il existe deux entiers relatifs u et Démontrer que N peut s’écrire sous la forme :
v tels que au + bv = 2, alors le PGCD de a et b est N = 1 + 17x = 5 + 13y où x et y sont deux entiers
égal à 2 ». relatifs vérifiant la relation 17x − 13y = 4.
4) On considère l’équation ( E) : x2 − 52x + 480 = 0, 3) Résoudre l’équation 17x − 13y = 4 où x et y sont des
où x est un entier naturel. entiers relatifs.
Proposition 4 : « Il existe deux entiers naturels non 4) En déduire qu’il existe un entier relatif k tel que
nuls dont le PGCD et le PPCM sont solutions de N = 18 + 221k.
l’équation ( E). »
63 L’équation diophantienne 5x − 8y = 1 admet comme solutions des couples d’entiers relatifs qui sont :
a toujours premiers entre eux. c jamais premiers entre eux.
b parfois premiers entre eux. d On ne peut pas déterminer si les entiers sont
premiers entre eux ou non.
Dans les exercices suivants, plusieurs réponses sont proposées. Déterminer celles qui sont exactes. Justifier.
70 Dans un chiffrement affine, la fonction de codage est définie par la fonction f ( x ) = 17x + 22 (voir tableau
de codage de l’activité 3 p. 29).
a Le codage de « HUIT » est « LYCA ».
b Le message « PZWC » veut dire « VRAI ».
c La seule solution dans Z2 de l’équation 17x − 26y = 1 est (23 ; 15).
d La fonction de décodage est : f −1 ( y) = 23y + 14.
a b q r
Étape 0 391 221 1 170
Étape 1
Étape 2
Étape 3
Un astronome a observé au jour J0 le corps céleste A, qui apparaît périodiquement tous les
105 jours. Six jours plus tard (J0 + 6), il observe le corps B, dont la période d’apparition est de
81 jours. On appelle J1 le jour de la prochaine apparition simultanée des deux objets aux yeux
de l’astronome.
Le but de cet exercice est de déterminer la date de ce jour J1 .
TP 3 Chiffrement de Hill
B Codage et décodage
Le chiffrement de Hill publié en 1929, est un chiffre polygraphique, c’est-à-dire qu’on ne chiffre
pas les lettres les unes après les autres, mais par « paquets ».
Voici un exemple « bigraphique », c’est-à-dire où les lettres sont regroupées deux à deux.
Étape 1 : On regroupe les lettres par 2. Chaque lettre est remplacée par un entier en utilisant
le tableau ci-dessous :
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
Étape 3 : Chaque couple (y1 ; y2 ) est transformé en un couple de deux lettres en utilisant le
tableau de correspondance donné dans l’étape 1. On regroupe ensuite les lettres.
étape 1 étape 2 étape 3
Exemple : TE
|{z} =⇒ (19, 4) =⇒ (13, 19) =⇒ NT
|{z}
mot en clair mot codé
b) À l’aide de la partie A, montrer que tout couple ( x1 ; x2 ) vérifiant les équations du sys-
tème (S2 ) vérifie aussi les équations du système :
x1 ≡ 16y1 + y2 (26)
( S3 )
x2 ≡ 11y + 5y2 (26)
1
c) Montrer que tout couple ( x1 ; x2 ) vérifiant les équations du système (S3 ) vérifie aussi les
équations du système (S1 ).
d) Écrire un algorithme sur le même principe que l’algorithme de chiffrage pour décoder un
mot.
e) Décoder le mot : PFXXKNU.
Ce mot étant de 7 lettres, ajouter la lettre W à la fin du mot pour avoir des paquets de
deux lettres. Le décodage terminé, on supprimera la lettre dont le code est W.
Récréation, énigmes
Repas gastronomique
28 personnes participent à un repas gastronomique. Le
prix normal est de 26 e sauf pour les étudiants et les en-
fants. Ces derniers paient respectivement 17 e et 13 e. La
somme totale recueillie est de 613 e.
Calculer le nombre d’étudiants et d’enfants ayant parti-
cipé au repas.
Proposer trois méthodes dont une algorithmique pour ré-
soudre ce problème.
Les nombres 3
premiers
Auto-évaluation
Des ressources numériques pour préparer
le chapitre sur manuel.sesamath.net @
1 Montrer que les nombres suivants sont des 4 Traduire avec une seule égalité de congruence les
nombres premiers : propositions suivantes :
1) n est divisible par 6.
1) 31 2) 47 3) 53 4) 61 5) 83
2) n est divisible par 3 et par 5.
3) n est divisible par 4 et par 6.
2 Sans calculatrice, à l’aide des critères de divisibi-
4) n est divisible par 8 et par 9.
lité par 3, 5 et 11 ou de la division par 7, montrer que
les nombres suivants ne sont pas premiers :
5 Traduire par une phrase les propositions sui-
1) 57 3) 143 5) 341 7) 319 vantes sans utiliser le mot « congruence » :
2) 91 4) 265 6) 427 8) 1581 1) n ≡ 0 (5).
2) si n ≡ 0 (4) et n ≡ 0 (5), alors n ≡ 0 (20).
3 Sans calculatrice, donner tous les diviseurs des
3) Si n 6 25 et si n 6≡ 0 (2), n 6≡ 0 (3), n 6≡ 0 (5)
nombres suivants :
alors n est premier.
1) 16 3) 24 5) 45 7) 63 4) Si p est premier et si ab ≡ 0 ( p), alors a ≡ 0 ( p) ou
2) 15 4) 36 6) 51 8) 91 b ≡ 0 ( p ).
51
Activités d’approche
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
101 102 103 104 105 106 107 108 109 110
111 112 113 114 115 116 117 118 119 120
121 122 123 124 125 126 127 128 129 130
131 132 133 134 135 136 137 138 139 140
141 142 143 144 145 146 147 148 149 150
Partie B : Justification
1) Pourquoi est-on sûr lorsqu’on entoure 7 que les multiples de 7 inférieurs à 49 sont déjà rayés
de la liste ?
2) On donne la propriété :
√
« Si n n’est pas premier, alors il admet un diviseur premier p tel que 2 6 p 6 n ».
Parmi les entiers naturels jusqu’à 150, pourquoi est-on sûr qu’une fois rayés tous les mul-
tiples de 2 à 11, tous les nombres non rayés sont premiers ?
Partie C : Algorithme
On désire automatiser ce procédé par un programme avec la calculatrice. On utilise pour cela
deux listes. À chaque fois que l’on « entoure » un nombre, dans le programme, on le transfère
de la liste L1 dans une liste L2 . La fonction E(x) correspond à la partie entière du nombre re.
6) Que devrait-on ajouter et modifier dans ce programme pour qu’il puisse afficher la liste des
nombres premiers inférieurs ou égaux à un entier N donné ?
7) Donner alors la liste des nombres premiers inférieurs ou égaux à 400. Combien y en a-t-il ?
Le but de cette activité est de déterminer tous les diviseurs de 567 à l’aide d’une décomposition
en produit de facteurs premiers.
1) Décomposer 567 en produit de facteurs premiers et vérifier qu’il existe deux entiers p et q
tels que : 567 = p4 × q.
2) Pourquoi un diviseur de 567 est-il de la forme pα q β avec 0 6 α 6 4 et 0 6 β 6 1 ?
× p0 p1 p2 p3 p4
q0
q1
ACTIVITÉ 3
Cette activité a pour objectif d’exploiter la décomposition en facteurs premiers à travers le
problème classique de « l’âge du capitaine ».
1. Définition et propriétés
A. Définition
DÉFINITION
Un nombre premier est un entier naturel qui admet exactement deux diviseurs : 1 et lui-
même.
C ONSÉQUENCES :
1 n’est pas un nombre premier (il n’a qu’un seul diviseur).
Un nombre premier p est un entier naturel supérieur ou égal à 2, soit : p > 2.
Les nombres premiers inférieurs à 100 sont :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97.
Si un entier naturel n n’est pas premier, il admet un diviseur d tel que : 2 6 d < n.
R EMARQUE : Un entier naturel non premier est parfois appelé un nombre composé.
PREUVE
• Si n est premier, il admet un diviseur premier : lui-même.
• Si n n’est pas premier, l’ensemble D des diviseurs d de n tels que : 2 6 d < n n’est pas
vide. D’après le principe du bon ordre, il admet donc un plus petit élément p.
Si p n’était pas premier, il admettrait un diviseur d′ tel que 2 6 d′ < p qui diviserait aussi n.
Ceci est impossible car p est le plus petit élément de D. Donc p est premier.
• On a donc p premier et n = p × q avec p 6 q. En multipliant cette inégalité par p, on obtient :
√
p2 6 pq ⇔ p2 6 n, soit p6 n
Pour montrer qu’un naturel n est premier, on utilise la contraposée du critère d’arrêt :
√
« Si n n’admet pas de diviseur premier p tel que 2 6 p 6 n, alors n est premier. »
Exercice d’application
Montrer que 109 est un nombre premier.
√
Correction On a 10 < 109 < 11. Donc si 109 n’est pas premier, il admet un diviseur premier
inférieur à 11.
On teste tous les nombres premiers strictement inférieurs à 11, soit : 2, 3, 5 et 7.
• Des règles de divisibilité, on déduit que 109 n’est divisible ni par 2, ni par 3, ni par 5.
• En effectuant la division euclidienne de 109 par 7, on obtient : 109 = 7 × 15 + 4.
109 n’est donc pas divisible par 7.
• Conclusion : 109 n’est pas divisible par 2, 3, 5, et 7 donc 109 est premier.
Exemple ALGO
PREUVE
Cette preuve, par l’absurde ou par contradiction est celle proposée au IIIe siècle av. J.-C., par
Euclide, dans son ouvrage « Les Éléments ».
Il en existe bien évidemment d’autres.
Supposons qu’il existe un nombre fini n de nombres premiers : p1 , p2 ,. . ., pi , . . ., pn .
Soit N un nombre entier non premier, supérieur à 2, tel que :
N = p1 × p2 × · · · × pi × · · · × pn + 1.
D. Crible d’Ératosthène
R EMARQUES :
1) Pour éliminer les multiples de a supérieurs à a, commencer à a2 , car les multiples infé-
rieurs à a ont déjà été éliminés. En effet, les multiples de a inférieurs à a2 sont aussi des
multiples de nombres inférieurs à a. Par exemple lorsqu’on élimine les multiples de 7, on
commence à partir de 49.
√
2) Si N = 150, comme 150 ≈ 12, 25, alors tout nombre composé sera éliminé en tant que
multiple de 2, 3, 5, 7 et 11.
Exemple Pour N = 100, on obtient le tableau suivant. Les nombres premiers sont colorés en
jaune :
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
C ONSÉQUENCES :
Si un nombre premier p divise un produit de facteurs premiers, alors p est l’un de ces
facteurs premiers.
Si un nombre n est un carré, alors toutes les puissances des facteurs de sa décomposition
en facteurs premiers sont paires.
Soit p1 ,p2 ,. . .,pk des nombres premiers distincts et α1 ,α2 ,. . .,αk des entiers naturels non nuls.
α α α α
Si, pour tout i ∈ {1, 2, . . . , k}, pi i divise un entier n, alors le produit p1 1 p2 2 . . . pk k divise
aussi l’entier n.
Correction
16 758 2 On présente la décomposition avec une barre
8 379 3 verticale où l’on écrit à droite, les diviseurs
2 793 3 premiers et, à gauche, le quotient des divi-
931 7 sions successives par ces diviseurs premiers
133 7 pris dans l’ordre croissant.
19 19
1 On a donc 16 758 = 2 × 32 × 72 × 19.
PREUVE
Soit n un entier naturel supérieur ou égal à 2.
• Si n est premier, alors n se décompose en lui-même.
Exercice d’application
Correction
• On détermine les facteurs premiers communs pour trouver le PGCD de ces deux nombres.
PGCD(126 ; 735) = 3 × 7 = 21.
β1 β2 βm
d = p1 × p2 × · · · × p m avec 0 6 β i 6 αi et i ∈ {1, 2, . . . , m}
R EMARQUES :
Le nombre de diviseurs d’un entier se calcule facilement car la puissance d’un facteur
premier pi peut varier de 0 à αi , ce qui fait (αi + 1) possibilités.
Pour qu’un entier n admette un nombre impair de diviseurs, les (αi + 1) doivent être
impairs, donc toutes les puissances αi doivent être paires. Le nombre n est alors un carré.
Exercice d’application
Correction
• Pour déterminer tous ses diviseurs, on peut utiliser un tableau à double entrée en séparant
les puissances de 2 et les puissances de 3 et 5. On obtient alors :
× 20 21 22 23
30 50 1 2 4 8
31 50 3 6 12 24
30 51 5 10 20 40
31 51 15 30 60 120
Les 16 diviseurs de 120 sont donc : D120 = {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120} .
• On peut aussi utiliser un arbre pondéré dont les coefficients sont les facteurs premiers
possibles.
d120
20 21 22 23
1 2 4 8
30 31
1 3 2 6 4 12 8 24
50 51
1 5 3 15 2 10 6 30 4 20 12 60 8 40 24 120
Exercice d’application
Un entier naturel n a 15 diviseurs. On sait de plus que n est divisible par 6 mais pas par 8.
Déterminer cet entier n.
Correction
• L’entier n a 15 diviseurs. Il faut donc connaître toutes les décompositions de 15 en facteurs
supérieurs à 1. Il n’y a que deux décompositions possibles soit en un seul facteur 15, soit en
deux facteurs 3 × 5.
• On sait que n est divisible par 6, il est donc divisible par 2 et par 3. Donc n admet au moins
deux facteurs premiers. Comme 15 ne peut se décomposer en plus de deux facteurs, alors n
ne peut admettre que deux facteurs premiers : 2 et 3. On a donc : n = 2α 3β .
• Comme on a 15 = 3 × 5 diviseurs, alors : (1 + α)(1 + β) = 3 × 5.
• On trouve alors deux solutions : α = 2 et β = 4 ou α = 4 et β = 2.
• On sait de plus que n n’est pas divisible par 8 = 23 , donc α est inférieur à 3. n est donc :
n = 22 34 = 4 × 81 = 324.
Exercice d’application
Déterminer le plus petit entier naturel possédant 28 diviseurs.
• En un facteur.
Le plus petit entier n est alors n = 2α avec α + 1 = 28, soit α = 27.
Donc n = 227 = 134 217 728.
• En deux facteurs : 28 = 4 × 7.
Le plus petit entier n est alors : n = 2α × 3β avec α + 1 = 7 et β + 1 = 4.
• En trois facteurs : 28 = 2 × 2 × 7.
Le plus petit entier n est alors : n = 2α × 3β × 5γ avec α + 1 = 7 , β + 1 = 2 et γ + 1 = 2.
On trouve : α = 6 , β = 1 et γ = 1, donc n = 26 × 3 × 5 = 960.
13 MÉTHODE 1 p. 55
1 Déterminer les nombres premiers parmi les en-
Sans calculatrice, à l’aide de divisions successives et du
tiers suivants : 39, 47, 51, 67, 77, 83, 91.
critère d’arrêt, déterminer si les entiers suivants sont
premiers ou non.
2 Citer tous les nombres premiers compris entre 30
et 60. 97 ; 117 ; 271 ; 323 ; 401 ; 527 ; 719
3 Soit a et b deux entiers naturels inférieurs ou 14 Montrer que 271 est premier. On expliquera clai-
égaux à 20. Le produit ab est divisible par 5. Quelles rement la méthode utilisée.
sont les valeurs possibles pour a et b ?
15 Donner la liste des nombres premiers inférieurs
à 50. Les nombres 577 et 689 sont-ils premiers ?
4 Soit p un nombre premier et n en entier naturel.
16 p est premier et p > 5.
Montrer que si p divise n2 , alors p2 divise n2 . 1) Démontrer que p2 − 1 est divisible par 3.
2) Démontrer que p2 − 1 est divisible par 8.
5 Soit a un entier naturel. 13 divise a5 .
3) En déduire que p2 − 1 est divisible par 24.
a5
Montrer que 134 divise . 17 Soit p soit un nombre premier tel que p > 3.
13
1) Quels sont les restes possibles dans la division de p
6 Décomposer mentalement les nombres suivants par 12 ?
en produits de facteurs premiers : 30, 40, 64, 70, 120, 2) Prouver que p2 + 11 est divisible par 12.
800, 2 000, 60 000. 18 Démontrer que pour tout n entier (n > 1), 30n + 7
n’est jamais la somme de deux nombres premiers.
7 On considère le nombre 6! (factoriel 6) défini par :
19 Soit le nombre N = 2n2 + n − 10 avec n ∈ N.
6! = 1 × 2 × 3 × 4 × 5 × 6.
1) Factoriser N.
Décomposer n en produit de facteurs premiers. 2) Pour quelles valeurs de n, le nombre N est-il
premier ?
8 Déterminer la décomposition en facteurs premiers 20 Vrai ou faux ?
de : 292 − 4 et 852 − 16. Soit le nombre N = 2n2 + 7n + 6 avec n ∈ N.
La proposition suivante est-elle vraie ou fausse ?
9 Déterminer le nombre de diviseurs de 48. Justifier.
« Il existe une valeur de n telle que N soit premier. »
10 Déterminer le nombre de diviseurs de 60.
21 On considère un entier n tel que n2 = 17p + 1, où
11 En optimisant la décomposition en produit de fac- p est premier.
teurs premiers, déterminer les entiers naturels, compris 1) Écrire 17p comme le produit de deux facteurs.
entre 2 et 50, qui possèdent le plus de diviseurs. 2) Citer le théorème de Gauss appliqué aux nombres
premiers.
12 En optimisant la décomposition en produit de fac- 3) En déduire n, puis p.
teurs premiers : déterminer les entiers naturels, compris 22 On considère un entier n tel que n2 = 29p + 1, où
entre 2 et 100, qui possèdent le plus de diviseurs. p est premier.
1) Écrire 29p comme le produit de deux facteurs en
fonction de n.
2) Citer le théorème de Gauss appliqué aux nombres 28 Déterminer PGCD( a ; b ) à l’aide d’une décompo-
premiers. sition en facteurs premiers, puis à l’aide de l’algorithme
3) En déduire n, puis p. d’Euclide des couples ( a ; b ) suivants :
1) a = 1 188 et b = 1 485 2) a = 3 780 et b = 3 528
23 Est-il possible de trouver un nombre premier p tel
29
que p + 1 000 et p + 2 000 soient aussi premiers ?
1) Déterminer le PGCD de 428 904 et 306 360 :
Aide : On pourra raisonner modulo 3, c’est-à-dire que a) à l’aide de l’algorithme d’Euclide ;
l’on analysera successivement les cas p ≡ 0, p ≡ 1 et b) à l’aide de la décomposition en facteurs premiers
p ≡ 2 modulo 3. de 428 904 et 306 360.
2) Quelle est la méthode la plus efficace ? Pourquoi ?
24 Nombres de Mersenne
30 MÉTHODE 4 p. 60
On appelle nombres de Mersenne, les nombres Mn de Décomposer 792 en produit de facteurs premiers. Quel
la forme : Mn = 2n − 1, avec n ∈ N*. est le nombre de diviseurs de 792 ? À l’aide d’un tableau
1) Calculer les six premiers nombres de Mersenne. ou d’un arbre déterminer tous les diviseurs de 792.
Quels sont ceux qui sont des nombres premiers ? 31 Décomposer 8 316 en produit de facteurs pre-
2) Soit n un entier naturel non nul et a un entier. miers. Quel est le nombre de diviseur de 8 316 ?
Montrer la factorisation standard : À l’aide d’un tableau ou d’un arbre déterminer tous les
an − 1 = ( a − 1)( an−1 + an−2 + · · · + a + 1). diviseurs de 8 316.
3) En déduire que, si d est un diviseur de n, Mn est
32 Trouver un nombre de trois chiffres qui soit un
divisible par 2d − 1.
carré parfait divisible par 56.
4) Montrer que, si Mn est premier, alors n est premier.
La réciproque est-elle vraie ? (On pourra calculer 33
M11 .) 1) Décomposer 2 016 en produit de facteurs premiers.
5) Soit a et n deux entiers tels que : a > 2 et n > 2. 2) Déterminer, en expliquant la méthode choisie, la plus
Montrer que si an − 1 est premier, alors a = 2 et petite valeur de l’entier naturel k pour laquelle k2 est
n est premier. un multiple de 2 016.
37 Un nombre n s’écrit 2α 3β où α et β sont deux en- 1) On pose p = 2. Montrer que l’équation (E) est sans
tiers naturels. Le nombre de diviseurs de 12n est le solution.
double du nombre de diviseurs de n. 2) On suppose désormais que p 6= 2 et que le couple
1) Montrer que l’on a : β(α − 1) = 4. ( x; y) est solution de l’équation (E). Le but des ques-
2) En déduire les trois valeurs possibles pour n. tions suivantes est de prouver que x et y sont pre-
38 Un entier n a 5 diviseurs et n − 16 est le produit miers entre eux.
de deux nombres premiers. a) Montrer que x et y sont de parités différentes.
1) Prouver que n = p4 , avec p premier. b) Montrer que x et y ne sont pas divisibles par p.
2) Écrire n − 16 sous forme d’un produit de trois fac- c) En déduire que x et y sont premiers entre eux.
teurs dépendant de p. 3) On suppose maintenant que p est une somme de
3) En déduire la valeur de n. deux carrés non nuls, c’est-à-dire que :
p = u 2 + v2 ,
39 Un détaillant de matériel audiovisuel effectue
où u et v sont deux entiers naturels strictement posi-
trois remises successives sur un article qui coûtait 300 e
tifs.
et qu’il vend 222,87 e.
a) Vérifier que le couple u2 − v2 ; 2uv est solu-
Quels sont les pourcentages (nombres entiers) des trois
tion de (E).
remises ?
b) Donner une solution de l’équation (E) lorsque :
40 Les zéros de 1 000 ! p = 5, puis lorsque p = 13.
L’exercice a pour but de déterminer par combien de zé- 4) On se propose enfin de vérifier, sur deux exemples,
ros se termine le nombre 1 000 ! (factorielle mille et non que l’équation (E) est impossible lorsque p n’est pas
« mille points d’exclamation ») la somme de deux carrés.
On rappelle que : 1 000! = 1 × 2 × 3 × · · · × 1 000. a) p = 3 et p = 7 sont-ils la somme de deux carrés ?
1) Montrer qu’il existe des entiers p et q (p > 1 et q > 1) b) Démontrer que les équations :
et un entier N premier avec 10 tels que : x2 + y2 = 9 et x2 + y2 = 49 n’admettent pas de
couples solutions d’entiers strictement positifs.
1 000! = 2 p × 5q × N.
a) Combien y a-t-il de nombres inférieurs ou égaux On appelle nombre parfait un nombre dont la somme
à 1 000 divisibles par 5 ? des diviseurs stricts est égal à lui-même.
b) Combien y a-t-il de nombres inférieurs ou égaux 1) Euclide donne la règle suivante pour trouver des
à 1 000 divisibles par 52 ? nombres parfaits :
c) Combien y a-t-il de nombres inférieurs ou égaux « Si un nombre a s’écrit 2n (2n+1 − 1) et si 2n+1 − 1 est
à 1 000 divisibles par 53 ? premier, alors a est parfait ».
d) Combien y a-t-il de nombres inférieurs ou égaux Exemples : Trouver les quatre premiers nombres
à 1 000 divisibles par 54 ? parfaits.
e) En déduire alors que q = 249. 2) Démonstration. On pose a = 2n (2n+1 − 1) et suppo-
3) Établir que p > q et que le nombre cherché est q. sons que 2n+1 − 1 est premier.
a) Quelle est la décomposition de a en produit de fac-
41 Triplets pythagoriciens teurs premiers ?
Soit p un nombre premier donné. On se propose d’étu- b) En déduire la liste des diviseurs de a.
dier l’existence de couples ( x; y) d’entiers naturels stric- c) Démontrer alors que la somme des diviseurs
tement positifs vérifiant l’équation : stricts est égale à ce nombre a.
2 2 2
(E) x +y = p .
4) Soit l’algorithme suivant où MOD( N, k) représente 2) Soient p et q deux entiers naturels non nuls.
le reste de la division euclidienne de N par k. a) En déduire que 2 pq − 1 est divisible par 2 p − 1.
b) En déduire que si un entier k supérieur ou égal
1. Liste des variables utilisées à 2 n’est pas premier, alors Mk ne l’est pas non
2. n : entier supérieur ou égal à 3 plus.
3. k : entier supérieur ou égal à 2 3) a) Prouver que le nombre de Mersenne M11 n’est pas
4. Entrées premier.
5. Saisir n b) Que peut-on en déduire concernant la conjecture
6. Donner à k la valeur de 2 de la question 1b ?
7. Traitements
8. Tant que (MOD(2n − 1 , k) 6= 0 et PARTIE B
√
k 6 2n − 1) faire Le test de Lucas-Lehmer permet de déterminer si un
9. Donner à k la valeur de k + 1 nombre de Mersenne donné est premier. Ce test utilise
10. Fin Tant que la suite numérique (un ) définie par u0 = 4 et pour tout
11. Affichage entier naturel n :
12. Afficher k
√ un+1 = u2n − 2.
13. Si k > 2n − 1 Alors
14. Afficher "Cas 1" Si n est un entier naturel supérieur ou égal à 2, le test
15. Sinon permet d’affirmer que le nombre Mn est premier si, et
16. Afficher "Cas 2" seulement si, un−2 ≡ 0 ( Mn ). Cette propriété est ad-
17. Fin Si mise dans la suite.
a) Qu’affiche cet algorithme si on saisit n = 33 ? 1) Utiliser le test de Lucas-Lehmer pour vérifier que le
Et si on saisit n = 7 ? nombre de Mersenne M5 est premier.
b) Que représente le Cas 2 pour le nombre de Mer- 2) Soit n un entier naturel supérieur ou égal à 3.
senne étudié ? Que représente alors le nombre k L’algorithme suivant, qui est incomplet, doit per-
affiché pour le nombre de Mersenne étudié ? mettre de vérifier si le nombre de Mersenne Mn est
c) Que représente le Cas 1 pour le nombre de Mer- premier, en utilisant le test de Lucas-Lehmer.
senne étudié ?
1. Liste des variables utilisées
45 D’après Bac (Asie - 2014) 2. u, M, n, i : entiers naturels
3. Entrées
PARTIE A 4. Saisir n > 3
5. Donner à u la valeur de 4
Pour tout entier naturel k > 2, on pose Mk = 2k − 1. 6. Traitements
On dit que Mk est le k-ième nombre de Mersenne. 7. Donner à M la valeur de ...
8. Pour i variant de 1 à ... faire
9. Donner à u la valeur de ...
1) a) Reproduire et compléter le tableau suivant, qui 10. Fin Pour
donne quelques valeurs de Mk : 11. Si M divise u Alors
12. Afficher M . . .
k 2 3 4 5 6 7 8 9 10 13. Sinon
Mk 3 14. Afficher M . . .
15. Fin Si
b) D’après le tableau précédent, si k est un nombre
premier, peut-on conjecturer que le nombre Mk est Recopier et compléter cet algorithme de façon à ce
premier ? qu’il remplisse la condition voulue.
46 Nombre d’éléments 10 p − 1
2) Prouver que Np = .
Soit (E) l’ensemble des entiers naturels écrits, en base 9
3) On se propose de démontrer que si p n’est pas pre-
10, sous la forme abba où a est un chiffre supérieur ou mier, alors Np n’est pas premier.
égal à 2 et b est un chiffre quelconque. On rappelle que pour tout nombre réel x et pour tout
Exemples d’éléments de (E) : 2 002 ; 3 773 ; 9 119. entier naturel n non nul :
On cherche le nombre d’éléments de (E) ayant 11
x n − 1 = ( x − 1)( x n−1 + x n−2 + · · · + x + 1).
comme plus petit facteur premier.
1) a) Décomposer 1 001 en produit de facteurs pre- a) On suppose que p est pair et on pose p = 2q, où q
miers. est un entier naturel plus grand que 1.
b) Montrer que tout élément de (E) est divisible Montrer que Np est divisible par N2 = 11.
par 11. b) On suppose p non premier et on pose p = kq où k
2) a) Quel est le nombre d’éléments de (E) ? et q sont des entiers naturels plus grands que 1.
b) Quel est le nombre d’éléments de (E) qui ne sont En déduire que Np est divisible par Nk .
ni divisibles par 2 ni par 5 ? c) Énoncer une condition nécessaire pour que Np
3) Soit n un élément de (E) s’écrivant sous la forme soit premier.
abba. Cette condition est-elle suffisante ?
a) Montrer que : « n est divisible par 3 » équivaut à
« a + b » est divisible par 3. 49 Divisibilité par 240
b) Montrer que : « n est divisible par 7 » équivaut à p est un nombre premier supérieur ou égal à 7.
« b est divisible par 7 ». Le but de cet exercice est de montrer que l’entier natu-
4) Déduire des questions précédentes le nombre d’élé- rel n = p4 − 1 est divisible par 240, puis d’appliquer
ments de (E) qui admettent 11 comme plus petit fac- ce résultat.
teur premier.
1) Peut-on avoir p ≡ 0 (3) ?
47 Vrai ou faux ?
En analysant les autres cas modulo 3, démontrer que
1) Soit n un entier naturel supérieur à 5. n est divisible par 3.
Proposition 1 : n2 − 3n − 10 n’est jamais un nombre
2) En remarquant que p est impair, prouver qu’il existe
premier.
un entier naturel k tel que :
2) Soit n un entier naturel supérieur ou égal à 3.
Proposition 2 : Pour tout entier k (2 6 k 6 n), p2 − 1 = 4k(k + 1).
le nombre n! + k n’est pas premier.
En déduire que p2 − 1 est divisible par 8 puis que n
48 Rep-unit est divisible par 16.
Un rep-unit (ou répunit) est un entier naturel dont 3) En raisonnant comme à la question 1) modulo 5, dé-
l’écriture ne comporte que des 1. Le nom provient de montrer que 5 divise n.
repated unit en anglais.
4) a) Que peut-on dire si a et b divise c et que
On se propose dans cet exercice d’étudier le problème
PGCD( a, b ) = 1 ?
suivant :
« Les nombres dont l’écriture décimale n’utilise que le b) Déduire des questions précédentes que 240 di-
seul chiffre 1 peuvent-ils être premiers ? » vise n.
Pour tout entier naturel p tel que p > 2, on pose : 5) Existe-t-il 15 nombres premiers p1 , p2 , . . ., p15 su-
Np = 1 . . . 1 où 1 apparaît p fois. périeurs à 7, tels que l’entier A ci-dessous soit un
On a alors : Np = 10 p−1 + 10 p−2 + · · · + 101 + 1. nombre premier ?
1) Les nombres N2 , N3 , N4 sont-ils premiers ?
A = p41 + p42 + · · · + p415
54 Pour établir la liste des nombres premiers inférieurs à 4 000 à l’aide du crible d’Ératosthène, on raye les
multiples des nombres premiers jusqu’à :
a 61 b 67 c 100 d 4 000
56 Parmi les phrases suivantes, quelles sont celles qui sont vraies ?
57 Parmi les phrases suivantes, quelles sont celles qui sont vraies ?
62 On donne l’algorithme suivant dans lequel E(x) désigne la partie entière du nombre x :
1) Montrer qu’il existe d unique tel que : 1 6 d < ( p − 1)(q − 1) et ed ≡ 1 [( p − 1)(q − 1)].
2) On rappelle le petit théorème de Fermat :
« Soit un nombre premier p et un entier naturel a non multiple de p, alors : a p−1 ≡ 1 ( p). »
3) On choisit p = 5, q = 7 et e = 7. Calculer d.
Commentaires
1) Un système à clef publique :
le couple (n ; e) connu de tout un chacun permet à « tout public » de transmettre un message
à Bob ;
le couple ( p ; q ) n’est connu que de Bob et lui permet d’être le seul à pouvoir déchiffrer le
message en calculant d.
2) La sécurité du système tient pour l’essentiel dans :
• la construction de nombres premiers « grands » (on sait le faire) ;
• la difficulté de décomposer un nombre grand (300 chiffres par exemple) en produit de
deux nombres premiers.
Mais personne ne sait si une attaque du RSA qui éviterait la factorisation est impossible !
H e l p espace !
072 101 108 112 032 033
Alice code ensuite ces nombres avec la fonction « trappe » de Bob : f B (m) = me (n).
Pour H, elle recherche m1e ≡ c1 (n) ⇔ 721 427 ≡ ? (2 173).
Inutile de s’acharner avec la calculatrice, elle se montrera incapable du calcul de 721 427
modulo 2 173. On a recours alors à une méthode dite d’exponentiation modulaire rapide.
a) Montrer que e = 1 427 s’écrit 210 + 28 + 27 + 24 + 2 + 1.
10 8 7 4
b) Montrer alors que : m1 427 = m2 × m2 × m2 × m2 × m2 × m.
c) On calcule ensuite les restes successifs a1 , a2 , . . ., a10 par la division par 2 173 de :
2 3 4 10
m, m2 , m2 , m2 , m2 , . . ., m2 .
Montrer alors que a10 × a8 × a7 × a4 × a1 × a0 ≡ c1 (2 173).
d) On propose le programme suivant pour coder le message d’Alice.
Ce programme calcule successivement les restes a1 , a2 ,. . ., a10 .
On range alors les dix restes dans une liste L1 .
Avant de lancer le programme, on a rentré dans une liste L2 les coefficients des puissances
de 2 de 1 427 : L2 = (1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1).
On cherche ensuite le reste du produit S des ai où le rang i dans L2 n’est pas nul.
Récréation, énigmes
Recherche d’un PGCD
Trouver le PGCD de 337 − 3 et de 1 221.
(Note : il y a du Fermat dans l’air ! !)
Conseils
La veille de l’épreuve
Pensez à préparer : votre calculatrice (piles neuves et en mode Examen – à partir de 2018), une règle, un compas,
plusieurs stylos de couleurs différentes (attention à ne pas utiliser le rouge) et une bouteille d’eau.
Les 5 premières minutes
Quand vous recevez le sujet, lisez bien les indications de la première page et vérifiez le nombre de pages, la quantité
d’exercices et les points associés. L’exercice portera la mention « obligatoire » ou « spécialité ». Lisez une première
fois les énoncés et choisissez dans quel ordre vous allez faire les exercices : par ordre croissant de difficulté (pour
vous).
Au cours de l’épreuve
Lisez attentivement les énoncés. Si vous n’arrivez pas à résoudre la question, ne perdez pas de temps : allez à la
question suivante ou à un autre exercice. Vous pourrez revenir à cette question plus tard. Changer de page pour un
nouvel exercice et laisser de l’espace pour revenir à une question non traitée.
Les 10 dernières minutes
Quand vous avez terminé, relisez votre copie. La qualité de la rédaction, la clarté et la précision de votre raisonne-
ment seront prises en compte dans l’appréciation de votre copie. Soignez votre écriture. Encadrez les résultats.
Vérifiez que vous avez bien indiqué votre nom dans le cartouche et que toutes vos pages sont dans la chemise.
Problèmes ouverts
Les problèmes ouverts se définissent comme des « énoncés courts qui n’induisent ni la méthode, ni la solution ». Il
est possible de s’engager dans des essais, des conjectures, des projets de résolution, des contre-exemples.
Problèmes de synthèse
Ils font appel à des notions étudiées dans différents chapitres avec des questions qui s’enchaînent. Ils permettent
de réactiver un ensemble de connaissances et d’établir des liens entre les chapitres.
QCM de synthèse
Ils permettent de vérifier l’acquisition des connaissances et des raisonnements en s’affranchissant de la rédaction.
PRÉPARER LE BACCALAURÉAT 75
PROBLÈMES OUVERTS
1 D’après Irem Lyon 8 Est-il vrai qu’un entier naturel qui a un nombre
On distribue des bonbons à n enfants placés en cercle impair de diviseurs est un carré parfait ?
en tournant toujours dans le même sens : on donne un
9 Soit a, b et c trois nombres premiers strictement
bonbon à un enfant, on passe le suivant, on donne un
supérieurs à 3.
bonbon au troisième, on passe les deux suivants, on
Le nombre a2 + b2 + c2 peut-il être premier ?
donne un bonbon au sixième, etc.
Pour quelles valeurs de n les enfants auront-ils tous au 10 Les côtés d’un terrain triangulaire mesurent
moins un bonbon ? 132 m, 156 m et 204 m. On veut planter des choux sur
son pourtour de façon qu’il y ait un chou à chaque som-
2 Dans le vivarium d’un zoo, vivent des caméléons
met du triangle et que les choux soient régulièrement
de couleurs unies : 13 oranges, 15 verts et 17 bruns. Lors
espacés d’un nombre entier de mètres.
d’une visite à ces grands lézards, Ali observe un curieux
Combien de choux au minimum doit-on planter ?
phénomène : lorsque deux caméléons de couleurs dis-
tinctes se croisent, ils prennent la troisième couleur. 11 Trois navires partent régulièrement d’un même
Comment organiser les rencontres pour que la popula- port : l’un tous les huit jours, l’autre tous les dix jours et
tion de caméléons soit unicolore ? le dernier tous les quinze jours.
Sachant qu’ils ont quitté le port ensemble un 11 mai,
3 En choisissant cinq entiers distincts au hasard, est-
quelle est la date du prochain départ commun ?
on sûr qu’à chaque fois la somme de trois d’entre eux
est un multiple de 3 ? 12 Soit un entier dont l’écriture a entre 4 et 6 chiffres
3x + 1 parmi 1, 3, 7 et 9 présents chacun au moins une fois.
4 Soit la fonction f : x 7→ .
x+1 Cet entier peut-il être divisible par 7 ?
Sa courbe représentative a-t-elle des points à coordon-
nées entières ? Si oui, les caractériser. 13 Existe-t-il un couple d’entiers naturels ( a ; b ) tel
a3 + 1
que le quotient soit un entier naturel ?
5 Les entiers naturels non nuls x, y, z sont les lon- ab − 1
gueurs des côtés d’un triangle ABC. 14 Crible de Matiassevitch
Démontrer que si le triangle ABC est rectangle en A
Soit a et b deux entiers naturels supérieurs à 2.
alors l’une au moins des longueurs de l’un des côtés
Dans un repère orhogonal, on place les points
est un multiple de 5.
A(− a ; a2 ), B(b ; b2 ) et M (0 ; m) le point d’intersec-
6 Un théâtre pratique deux tarifs : 19 e pour les tion de la droite ( AB) avec l’axe des ordonnées.
abonnés et 29 e pour les autres. Conjecturer l’ensemble des valeurs que m ne peut pas
À la fin d’une représentation, la caissière a égaré les prendre, à l’exception de 0 et de 1.
souches des billets mais elle est sûre d’avoir fait 818 e Démontrer cette conjecture.
de recette. Aider la caissière à retrouver la répartition
des tickets vendus pour rendre compte au gérant.
9
7 La figure ci-dessous est formée de trois carrés.
8
L’unité de mesure est le cm et les mesures des côtés des
7
carrés sont des entiers naturels.
6
16 cm
5
16 cm
4
3
2
Quelles sont les mesures des côtés des carrés sachant 1
que l’aire de la figure est divisible par 10 et inférieure à
5 000 cm2 ? −3 −2 −1 1 2 3
76 PROBLÈMES OUVERTS
15 L’ADN est une séquence de nucléotides dont les 20 Un message codé en binaire est transmis via un
quatre bases essentielles sont l’adénine (1), la thymine réseau. À chaque étape du réseau, la probabilité qu’un
(2), la guanine (3) et la cytosine (4). bit (0 ou 1) soit transmis sans erreur est 0, 01.
La matrice de transition suivante représente les proba- Quelle est la probabilité qu’un octet (huit bits consécu-
bilités de successions des quatre bases : tifs) soit transmis sans erreur ?
0, 3 0, 21 0, 29 0, 2 21 En temps normal, l’équilibre de deux substances
A et B présentes dans le corps d’un koala garantit sa
0, 17 0, 3 0, 3 0, 23
0, 25 0, 2
0, 3 0, 25 bonne santé. Mais chez un koala malade, les quantités
0, 32 0, 3 0, 08 0, 3 de A et B fluctuent et l’on doit injecter chaque mois une
quantité q en mg par litre de sang de substance A.
Donner les successions la moins et la plus probables.
Ainsi, d’un mois n à l’autre, les quantités en mg par litre
16 Un agent fait sa ronde autour d’un parc de forme de sang, an (A) et bn (B), sont régies par l’égalité :
hexagonale. À chaque angle, il lance un dé : si c’est pair, ! ! ! !
il continue dans le même sens ; sinon, il change de sens. a n+1 0, 3 0, 7 an q
= + .
Un être mal intentionné, qui connaît la combine, a-t-il bn+1 −0, 2 1, 3 bn 0
plutôt intérêt à vouloir entrer dans le parc par un en- Pour guérir le koala, il faut stabiliser la quantité de sub-
droit plutôt qu’un autre ? stance B autour de 1 000 mg par litre de sang.
17 Soit deux suites de matrices (Un ) et (Vn ) définies, Quelle quantité q de substance A faut-il injecter chaque
pour tout n ∈ N, par : mois au koala pour y parvenir ?
Un+1 = 0, 8Un + 3 et Vn+1 = −0, 6Un + 1, 25Vn + 4 22 Un réseau de lignes de bus qui relie cinq villages
A, B, C, D et E est représenté par un graphe dont la
Les suites (Un ) et (Vn ) sont-elles convergentes ? Si oui, matrice est, avec les villes dans l’ordre alphabétique :
déterminer à quelles conditions, exprimées en fonction
des matrices initiales U0 et V0 . 0 1 0 1 0
1 0 0 1 0
18 Après le débat de l’entre-deux-tours, un candi-
M=
0 0 0 0 1
dat à la présidence voit sa cote de popularité évoluer
1 1 0 0 0
chaque jour de la façon suivante :
0 0 1 0 0
3 % de ses partisans deviennent ses détracteurs ;
3,5 % de ses détracteurs deviennent ses partisans. Par exemple, m12 = m21 = 1 signifie que les villages A
Le candidat a recueilli 41 % des suffrages au premier et B sont directement reliés et m13 = m31 = 0 que les
tour. Peut-il espérer l’emporter dans une semaine ? villages A et C ne sont pas directement reliés.
Quels villages ne sont pas reliés en au plus cinq arrêts ?
19 Chococam, une entreprise de barres chocolatées,
lance une opération commerciale en glissant dans 23 La firme FEZ lance une campagne de publi-
chaque paquet le poster d’une équipe ayant fini sur le cité pour augmenter les ventes d’un produit qu’elle
podium de la coupe d’Afrique des Nations. commercialise et que seulement 30 % des clients lui
On admet qu’il y a assez de paquets sur le marché pour achètent. Elle apprend qu’au bout d’une semaine :
considérer que les posters sont toujours équirépartis. 20 % des clients qui achetaient à la concurrence
1) Chococam matraque qu’en achetant six paquets, on achètent maintenant chez FEZ ;
a trois chances sur quatre d’avoir les trois posters. 10 % des clients qui achetaient chez FEZ achètent
Chococam fait-elle de la publicité mensongère ? maintenant à la concurrence.
2) Un client peut-il être sûr d’obtenir les trois posters ? On suppose que le comportement des clients ne change
Si oui, déterminer le nombre de paquets qu’il doit pas. La campagne de FEZ fonctionnera-t-elle ? Si oui,
acheter au minimum. déterminer à partir de combien de semaines.
PROBLÈMES OUVERTS 77
PROBLÈMES DE SYNTHÈSE
(
Pour les exercices 1 et 2 relatifs au chiffrement de 3x1 + x2 ≡ 3x1′ + x2′ [26]
a) Montrer que .
Hill, on utilisera la table de correspondance suivante. 5x1 + 2x2 ≡ 5x1′ + 2x2′ [26]
( (
x1 ≡ x1′ [26] x1 = x1′
A B C D E F G H I J K L M b) En déduire que puis .
x2 ≡ x2′ [26] x2 = x2′
0 1 2 3 4 5 6 7 8 9 10 11 12 3) On souhaite décoder DP pour revenir! à DP.
N O P Q R S T U V W X Y Z 2 −1
a) Vérifier que C −1 = .
13 14 15 16 17 18 19 20 21 22 23 24 25 −5 3
b) Calculer y1 y2 = 3 15 C −1.
1 D’après Bac (Antilles-Guyane - septembre 2013) (
x1 ≡ y1 [26]
PARTIE A c) Calculer x1 x2 tels que .
x2 ≡ y2 [26]
On considère l’algorithme suivant : 4) On cherche à généraliser
une
procédure
de décodage
pour passer de z1 z2 à x1 x2 .
1. A et X sont des entiers
Soit y1′ y2′ = z1 z2 C −1.
2. Saisir un entier positif A (
3. Affecter à X la valeur de A
x1 ≡ y1′ [26]
Soit x1 x2 telle que .
4. Tant que X supérieur ou égal à 26 x2 ≡ y2′ [26]
(
5. Affecter à X la valeur X - 26 3x1 + x2 ≡ z1 [26]
Montrer que .
6. Fin du tant que 5x1 + 2x2 ≡ z2 [26]
7. Afficher X 5) Conclure et décoder QC.
78 PROBLÈMES DE SYNTHÈSE
On admet que 21 est l’unique entier k tel que : 4) On admet l’existence, c’est-à-dire que toute fraction
0 6 k 6 25 et 5k ≡ 1 [26]. irréductible existe dans l’arbre.
On veut montrer l’unicité, c’est-à-dire montrer
1) Coder le mot ET. (
qu’aucune fraction n’apparaît plus d’une fois dans
5x1 = 2y1 − y2
2) Démontrer que : . l’arbre.
5x2 = −3y1 + 4y2 a a′
a) Soit deux fractions et ′ de l’arbre.
3) En utilisant la(question 3 de la partie A, établir que : b b
x1 ≡ 16y1 + 5y2 [26] a a + a′ a′
. Démontrer que < < .
b b + b′ b′
x2 ≡ 15y1 + 6y2 [26] b) En déduire l’unicité.
4) Décoder le mot QP.
PROBLÈMES DE SYNTHÈSE 79
PARTIE A : Nombres triangulaires carrés 5 Un code d’entrée d’immeuble noté abcdk est
constitué de cinq chiffres décimaux :
1) Montrer que 36 est un nombre triangulaire, et qu’il les quatre premiers chiffres a, b, c, d forment l’identi-
est aussi le carré d’un entier. fiant de chaque locataire ;
2) a) Montrer que le nombre 1 + 2 + . . . + n est le carré le cinquième chiffre k est une clé de contrôle.
d’un entier si, et seulement si, il existe un entier Lorsqu’un code est tapé au clavier, un ordinateur fait
naturel p tel que : n2 + n − 2p2 = 0. un test puis un autre si le premier est réussi :
b) En déduire que le nombre 1 + 2 + . . . + n est le
TEST1 : vérification de la validité du code.
carré d’un entier si, et seulement si, il existe un
TEST2 : authentification d’un locataire.
entier naturel p tel que : (2n + 1)2 − 8p2 = 1.
Voici l’algorithme de TEST 1 (où a%b donne le reste de
la division euclidienne de a par b).
PARTIE B : Étude d’une équation diophantienne
On considère (E) l’équation diophantienne :
1. A est une matrice carrée d’ordre 2
x2 − 8y2 = 1 2. U est une matrice ligne de taille 2
où x et y désignent deux entiers relatifs. 3. V est une matrice colonne de taille 2
1) Donner deux couples d’entiers naturels inférieurs à 4. a, b, c, d, r, k sont!entiers naturels
2
10 qui sont solution de (E). 5. U prend la valeur
3
2) Démontrer que, si ( x ; y) est solution de (E), alors x
et y sont premiers entre eux. 6. V prend la valeur 1 2
7. Afficher "Entrez votre code :"
PARTIE C : Lien avec le calcul matriciel ! 8. Saisir a, b, c, d, k
3 8
!
Soit deux entiers relatifs x et y, la matrice A = a b
1 3 9. A prend la valeur
! ! c d
x ′ x 10. r prend la valeur V*A*U+k
et deux entiers relatifs x ′ et y′ tels que =A .
y′ y 11. Si R%7=0 alors TEST2
1) Exprimer x ′ et y′ en fonction de x et de y.
2) Déterminer la matrice A−1 , puis exprimer x et y en 1) Tester l’algorithme avec le code 49173.
fonction de x ′ et y′ . Est-ce un code valide ?
3) Démontrer que ( x ; y) est solution de (E) si et seule- 2) Soit un code abcdk et n = 2a + 3b + 4c + 6d + k.
ment si ( x ′ ; y′ ) est solution de (E). Démontrer que si le code est valide, alors n ≡ 0 [7].
4) On définit les suites ( xn ) et (yn ) par !
x0 = 3 et y0!= 1 3) Un locataire entre le code 14135 qui est refusé.
xn+1 xn
et, pour tout entier naturel n, =A . Cependant, il n’est pas sûr du premier chiffre.
yn+1 yn
a) Déterminer un chiffre z tel que 2z ≡ 3 [7].
On admet que, pour tout n ∈ N, xn et yn sont des
b) Retrouver le premier chiffre du code du locataire.
entiers naturels.
4) Un autre locataire intervertit les 2e et 3e chiffres de
Démontrer par récurrence que, pour tout n ∈ N, le
son code. Pourra-t-il entrer ?
couple ( xn ; yn ) est solution de (E).
5) Un troisième locataire entre un code en se trompant
PARTIE D : Retour au problème initial sur le premier chiffre mais la porte s’ouvre quand
À l’aide des parties précédentes, déterminer un nombre même.
triangulaire supérieur à 2 015 qui est le carré d’un entier. Expliquer comment cela est possible.
80 PROBLÈMES DE SYNTHÈSE
QCM BILAN
Pour chaque question, déterminer la ou les réponse(s) exacte(s). Justifier.
3 On se propose de résoudre l’équation (E) : 24x + 34y = 2, où x et y sont des entiers relatifs.
QCM BILAN 81
8 On lance une pièce équilibrée et on veut obtenir au moins quatre fois consécutives le même résultat.
On a plus d’une chance sur deux d’y parvenir à partir d’un nombre de lancers égal à :
a 5 b 11 c 17 d 23
! ! ! !
0, 5 0, 45 0, 2 0, 24
9 Une matrice de transition M vérifie : M = et M = .
0, 5 0, 55 0, 8 0, 76
Alors M2 est égale
! à: ! ! !
2/3 1/6 0, 64 0, 0784 4/9 3/7 0, 66 0, 17
a b c d
1/3 5/6 0, 36 0, 9216 5/9 4/7 0, 34 0, 83
11 Si A et B sont deux matrices carrées non nulles d’ordre n telles que AB = λIn où λ ∈ R, alors :
a il existe λ tel que A n’est pas inversible c pour tout λ 6= 0, A−1 = B
1
b pour tout λ 6= 0, B−1 = A d pour tout λ, BA = λIn
λ
1 1 2a
Soit la matrice A = 2 1 . Déterminer la valeur de a pour laquelle la matrice n’est pas inversible.
12 1
1 1 3a
1
a a=1 b a = 0, 5 c a= d a=0
3
13 Une marche aléatoire entre trois états A, B et C est définie par le graphe suivant :
0,1
0,7 0,6
0,3 A B C 0,6
0,3 0,4
L’état initial est l’état A. La probabilité d’être dans l’état B à l’étape 5 vaut à 10−3 :
a 0,151 b 0,334 c 0,343 d 0,353
14 A et B sont deux usines. Chaque année, 44 % des ouvriers de A rejoignent B et 4 % des ouvriers de B
rejoignent A. Aujourd’hui, A et B ont 3 000 ouvriers chacune mais dans un futur lointain :
a A n’aura plus d’ouvriers c B comptera environ 2 750 ouvriers
b la répartition sera la même d A comptera environ 11 ouvriers
82 QCM BILAN
MATRICES
1
Matrices : opérations
Auto-évaluation
Des ressources numériques pour préparer
le chapitre sur manuel.sesamath.net @
1 Dans la gravure La Melancolia d’Albrecht Dürer, 2
on peut voir le tableau de 4 lignes et de 4 colonnes sui- 1) Résoudre
( les systèmes linéaires
( suivants :
vant : 5x + 2y = −4 12x + 15y = 112, 5
a) c)
7x + 3y = 6 8x + 10y = 75
( (
3x − 9y = −1 2x + y = 5
b) d)
−2x + 6y = 1 3x + 2y = 7
2) Que peut-on dire des tableaux suivants ?
5 2 3 −9
7 3 −2 6
On écrit un système correspondant à ce tableau où le
12 15 2 1
second membre est toujours égal à 34 :
8 10 3 2
16x + 3y + 2z + 13t = 34
On se place dans un repère du plan.
5x + 10y + 11z + 8t = 34 3
9x + 6y + 7z + 12t = 34 1) Démontrer que les droites (d′ ) : x + y=3, (d) : x =2
et (d′′ ) : y=2x − 3 sont concourantes.
4x + 15y + 14z + t = 34
2) Soit trois points A(1 ; 1), B(7 ; 1) et C (3 ; 3).
1) Vérifier que (1 ; 1 ; 1 ; 1) est solution de ce système.
Déterminer les coordonnées du centre de gravité du
2) Soit ai,j le coefficient situé dans la i-ième ligne et la
triangle ABC.
4 4
j-ième colonne. Montrer que ∑ ai,i = ∑ a5−i,i .
i =1 i =1 4 Déterminer le polynôme P de degré 2 vérifiant
3) La i-ième ligne du tableau devient la i-ième colonne
les conditions données.
d’un nouveau tableau.
1) P(0) = −1, P(0, 5) = 1 et P(−2) = 1.
Écrire le nouveau système correspondant où le
2) P(1) = 1, P′ (1) = 1 et P(−1) = 0.
second membre est toujours égal à 34.
83
Activités d’approche
1) La taille d’une matrice est donnée sous la forme : nombre de lignes × nombre de colonnes.
Déterminer la taille de la matrice A.
2) On note aij et on appelle coefficient le nombre situé dans la i-ième ligne et la j-ième colonne.
Quel est le coefficient a21 ? À quoi correspond t-il ?
3) Faire un second tableau qui présente les mêmes informations que le premier en permutant
les lignes et les colonnes. Écrire la matrice A′ correspondante.
A′ est appelée transposée de A et on la note AT .
4) À quel coefficient de A le coefficient a′ij de A′ est-il égal ?
Ci-après, la matrice T représente les temps du tableau et la matrice colonne V la vitesse moyenne
(en km · h−1 ) de chaque moyen de transport (de haut en bas : avion, train, voiture).
0 6 1, 5 750
T = 1, 5 0 0, 3 V = 210
1 1 0, 1 90
1) a) Déterminer la distance totale parcourue par chaque ami et inscrire les résultats dans une
matrice colonne D (de haut en bas, Ulrich, Manolo et Jules).
b) Exprimer le coefficient dij de D en fonction des coefficients des matrices T et V.
On dit que la matrice D est le produit de la matrice T par la matrice V. On note D = TV.
2) À partir du tableau ci-contre qui donne l’impact CO2 Impact CO2 Prix
(en kg) et le prix (en e) pour une heure passée dans Avion 111 172,5
chaque moyen de transport, on souhaite calculer l’im- Train 0,546 33,6
pact et le prix du trajet de chacun des amis. Voiture 1,035 5,4
a) Écrire la matrice M de taille 3 × 2 correspondant au tableau ci-dessus.
b) Calculer la matrice produit TM en fusionnant le produit de T par la première colonne
de M, puis le produit de T par la deuxième colonne de M.
c) Qui a fait le trajet le plus économique ? le plus écologique ?
3) a) On utilise un tableur (voir ci-dessous). Quelle formule doit-on inscrire dans la cellule D4
et étendre dans la plage de couleur bleu pour retrouver les résultats précédents ?
A B C D E F
1 750 111 172,5
2 210 0,546 33,6
3 90 1,035 5,4
4 0 6 1,5
5 1,5 0 0,3
6 1 1 0,1
b) Écrire l’égalité de matrices relative à la feuille de calcul sous la forme = .
4) L’an prochain, Ulrich, Manolo et Jules partiront Avion Train Voiture
à Honolulu avec Hermine, une surfeuse ren- Ulrich 15,25 0 5,8
contrée à Lacanau. Le tableau ci-contre fournit Manolo 15 0 3
les temps (en heures) qu’ils passeront dans les Jules 15 3 0,8
transports pour rejoindre leur destination. Hermine 15,5 0,5 0,1
a) Utiliser un tableur pour déterminer qui a fait le trajet le moins long, qui a fait le trajet le
moins écologique et qui a fait le trajet le moins économique.
b) Écrire l’égalité de matrices relative au calcul précédent.
Élise a réussi l’exercice. Elle met son amie Lilou 1. x, y, r, s sont des réels
dans la peau d’Enak qui vérifie que cela fonc- 2. Saisir r, s
tionne. « Passe-moi ton programme ! » dit-elle. 3. Affecter à x la valeur 2r-5s
Mais Élise, qui ne veut pas trop l’aider, ne lui 4. Affecter à y la valeur –r+3s
montre que l’algorithme ci-contre. 5. Afficher x, y
1. Définitions et vocabulaire
DÉFINITION : Matrice
Une matrice de taille m × n est un tableau de nombres formé de m lignes et n colonnes qui
s’écrit sous la forme :
n colonnes
a11 a12
· · · a1n
a21 a22 · · · a2n
m lignes ··· ··· ··· ···
am1 am2 · · · amn
Le nombre aij (avec 1 6 i 6 m et 1 6 j 6 n) est situé dans la i-ième ligne et la j-ième colonne.
Il est appelé un coefficient de la matrice.
R EMARQUE : En général, on note une matrice avec une lettre majuscule ou avec le coefficient
général entre parenthèses, par exemple ( aij ).
Si i > 9 ou j > 9, on écrira par exemple a1,11 et pas a111 pour éviter la confusion avec a11,1 .
!
4 7 −5
Exemple Soit A = ( aij ) la matrice de taille 2 × 3 égale à .
3 −1 8
Le coefficient a12 vaut 7. Le coefficient a21 vaut 3.
! !
4 cos θ − sin θ
Exemple A= 4 −2 1 ,B= et C = sont respectivement une
−2 sin θ cos θ
matrice ligne de taille 3, une matrice colonne de taille 2 et une matrice carrée d’ordre 2.
1 0 0
Exemple L’identité d’ordre 3 est I3 = 0 0. On peut aussi la noter diag(1, 1, 1).
1
0 0 1
R EMARQUE : S’il n’y a pas d’ambiguïté, on note l’identité I sans préciser son ordre en indice.
!T 1 4 !T ! !
1 2 3 1 2 1 3 T 0, 3
; ; .
Exemple = 2 5 = 0, 3 0, 7 =
4 5 6 3 4 2 4 0, 7
3 6
! ! ! !
−3 5 2 −5 −3 + 2 5−5 −1 0
Exemple Soit A = et B = . A+B = = .
−1 3 4 0 −1 + 4 3+0 3 3
PROPRIÉTÉ
Soit A, B, C trois matrices de même taille.
A + B = B + A (commutativité) ( A + B) + C = A + ( B + C ) (associativité)
! !
−3 5 −5 2
Exemple Soit A = et B = .
−1 3 4 0
! ! ! !
−3 5 −2 5 −3 − 2 5+5 −5 10
A − B = A + (− B) = + = = .
−1 3 −4 0 −1 − 4 3+0 −5 3
!
3, 5 −5 2, 5
Exemple A= .
−1 0, 5 −5, 5
! !
−2 × 3, 5 −2 × (−5) −2 × 2, 5 −7 10 −5
Alors, −2A = = .
−2 × (−1) −2 × 0, 5 −2 × (−5, 5) 2 −1 11
PROPRIÉTÉ
Soit A et B deux matrices de même taille et deux réels k et k′ .
0A = 0 et 1A = A (k + k′ ) A = kA + k′ A
k( A + B) = kA + kB (kk′ ) A = k(k′ A)
R EMARQUE : Dans l’égalité 0A = 0, le 0 de gauche est un réel mais celui de droite désigne
la matrice nulle, matrice ayant la même taille que A et dont tous les coefficients sont nuls.
−1
Exemple Soit A = −2 et B = −4. AB = 3 × (−1) + 0 × (−4) − 2 × (−2) = 1.
3 0
−2
R EMARQUES :
Le produit d’une matrice A par une matrice B n’existe qu’à condition que le nombre de
colonnes de A soit égale au nombre de lignes de B.
Si le produit d’une matrice A par une matrice B existe, en général, il n’est pas commutatif :
en premier lieu, BA n’existe pas toujours (il n’existe que si A et B sont des matrices carrées)
et, même si c’est le cas, généralement on n’a pas AB = BA.
Pour calculer la matrice C égale à AB, on vérifie que le nombre de colonnes de A est égal au
B
nombre de lignes de B, puis on dispose les matrices suivant le schéma de sorte que
A C
cij soit à l’intersection du prolongement de la i-ème ligne de A et de la j-ième colonne de B.
2 1 −3
!
Exercice d’application Soit A =
1 3 5 −2 3 −1 0
et B = . Calculer AB.
−2 0 −3 2 0
−2 2
2 −3 −4
Correction
A est de taille 2 × 4 et B de taille 4 × 3. 2 1 −3
A a autant de colonnes que B a de lignes, donc 3 −1 0
C = AB existe et sa taille est 2 × 3. 0 −2 2
On dispose les matrices comme ci-contre. 2 −3 −4 !
!
On calcule alors, par exemple : 1 3 5 −2 7 −6 15
c11 = 1 × 2 + 3 × 3 + 5 × 0 − 2 × 2 = 7. −2 0 −3 2 0 −2 −8
R EMARQUE : Il n’est pas nécessaire que l’une des matrices A ou B soit nulle pour que AB=0.
! ! !
1 −1 1 2 3 0 0 0
Exemple Soit A = et B = . Alors, AB = .
0 0 1 2 3 0 0 0
PROPRIÉTÉS
Soit A, B et C trois matrices compatibles avec les produits écrits ci-après et soit k un réel.
( AB)C = A( BC ) = ABC (associativité)
A( B + C ) = AB + AC et ( A + B)C = AC + BC (distributivité)
(kA) B = A(kB) = k( AB)
AI = I A = A et A0 = 0A = 0
! ! ! ! !
2 0 1 0 2 0 2 0 4 0
Exemple Soit A = . Alors, A0 = ; A2 = = .
0 −3 0 1 0 −3 0 −3 0 9
!
2n 0
On peut démontrer par récurrence que, pout tout n ∈ N, An = .
0 (−3)n
Correction
3. Matrices inversibles
A. Inverse d’une matrice carrée
DÉFINITION : Inverse d’une matrice carrée
Une matrice carrée A d’ordre n est inversible s’il existe une matrice carrée B d’ordre n telle
que AB = BA = I.
La matrice B, notée A−1 , est appelée la matrice inverse de A.
! ! !
3 5 7 −5 1 0
Exemple Soit A = et B = . AB = BA = donc B est l’inverse de A.
4 7 −4 3 0 1
PROPRIÉTÉ
Si une matrice est inversible, alors son inverse est unique.
PROPRIÉTÉ
1 1 0 −1 −1 0 1 0 0
Soit A = −2 0 et B = 2 0. Alors, AB = 0 0 = I.
Exemple −1 1 1
3 −2 1 7 5 1 0 0 1
Donc A et B sont inverses l’une de l’autre et on a les égalités A−1 = B et B−1 = A.
! ! ! !
d−b a b d −b ad − bc 0
PREUVE Soit N = . Alors, MN = = .
−c a c d −c a 0 ad − bc
1 1
• Si ad − bc 6= 0, alors MN = I ⇔ M N = I.
ad − bc ad − bc !
1 1 d −b
Donc M est inversible et son inverse est N= .
ad − bc ad − bc −c a
• Si ad − bc = 0, alors MN = 0. Supposons alors que M soit inversible, d’inverse P.
Alors, on aurait PMN = IN = N et PMN = P0 = 0 et donc N = 0, ce qui est absurde.
R EMARQUES :
Toute matrice carrée admet un déterminant et un seul, mais pour un ordre strictement su-
périeur à 2, il n’existe pas de formule simple pour le calculer et on utilisera une calculatrice
ou un logiciel de calcul formel (voir Méthode 4 p. 94).
Le déterminant non nul est un critère d’inversibilité d’une matrice carrée de tout ordre.
!
3 8 3 8
A= . Alors, det( A) = = 3 × 6 − 2 × 8 = 18 − 16 = 2 6= 0.
Exemple
2 6 2 6
! !
1 6 −8 3 −4
Ainsi, A est inversible et A−1 = = .
2 −2 3 −1 1, 5
! ! ! ! ! (
a b x c ax + by c ax + by = c
PREUVE = ⇔ = ⇔ .
a′ b′ y c′ a′ x + b′ y c′ a′ x + b′ y = c′
x ! ! (
2 −3 1 7 2x − 3y + z = 7
Exemple y = correspond au système .
3 −2 −1 −5 3x − 2y − z = −5
z
PROPRIÉTÉ
Soit A une matrice carrée inversible d’ordre n et B une matrice colonne de taille n.
Alors, le système linéaire d’écriture matricielle AX = B admet une unique solution :
le n-uplet correspondant à la matrice colonne A−1 B.
2x − 3y + 4z
= −1
Exercice d’application Résoudre le système linéaire x + y − 5z = 2 .
−4x + 3y = 6
◮ Ainsi, det( A) = −2 6= 0 donc A est inversible et le système admet une unique solution : le
triplet (−37, 5 ; −48 ; −17, 5).
Activités mentales x α a b c
7 Soit A = y , B = β et C = d e f .
36 Une entreprise doit fabriquer 80 ordinateurs α et 0 2 5
42 Soit A = 0 0 −2 et I l’identité d’ordre 3.
50 ordinateurs ω à partir d’unités de ressources.
Le tableau suivant fournit le nombre d’unités néces- 0 0 0
saires à la fabrication de chaque modèle et le coût de 1) Calculer I et An .
n
−1 1 2 −1 0 0 1) Écrire la matrice A des niveaux de gris de l’image
48 Soit A= 0 −1 −2 et D= 0 −1 0 .
précédente où les trois couleurs sont noir, blanc et
0 0 −1 0 0 −1 gris moyen (niveau 0,5).
1) Soit la matrice B = A − D. Calculer B2 et B3 . 2) a) Écrire la matrice B du négatif de cette image.
2) Démontrer que, pour tout entier naturel n > 3, on a : b) Exprimer bij en fonction de aij .
c) Représenter l’image correspondante à BT .
n ( n − 1) 2
An = (−1)n I3 − nB + B . 1 1 1 1 1 0
2 0 1 0 1 1 0
0 1 1 1 1 0 .
3) Soit C =
3 1 2 0 1 0 1 1 0
49 Soit la matrice A = 0 3 −1.
0 1 1 1 1 1
0 0 3 a) Décrire l’influence du facteur k sur l’image repré-
1) Déterminer une matrice diagonale B et une autre ma- sentée par kC pour k ∈]0 ; 1[.
trice C telle que A = B + C. b) Déterminer la matrice D telle que D = 2A − C.
2) a) Pour tout entier n, donner l’expression de Bn . c) Représenter l’image correspondante à D.
b) Vérifier que B et C sont commutatives.
c) Démontrer que, pour tout n ∈ N ∗ : 1 1 1
53 Soit la matrice triangulaire A = 0 1 1.
n n n n 2 n−2
A = B + nCB + C B . 0 0 1
2
1) a) A est triangulaire supérieure. Que dire de AT ?
50 Soit A la matrice carrée d’ordre 4 telle que aij = 0 b) Calculer A + AT − I.
si i > j et aij = i + j si i < j. 2) a) Calculer A2 , A3 , A4 et conjecturer An .
1) Écrire A. Quelle particularité a-t-elle ? b) Démontrer la conjecture par récurrence.
2) Déterminer An pour tout entier naturel n. ! !
2 1 1 6
54 Soit A = ,B= et C = A + B.
Calculs matriciels divers 5 3 −1 2
1) Calculer C 2 .
2) Calculer A2 + 2AB + B2 .
! !
1 −2 −1
51 Soit A = 4 0 ,B= ,C= . 3) Pourquoi n’a-t-on pas C 2 = A2 + 2AB + B2 ?
−3 −5 2
55 Soit A et B deux matrices carrées commutatives.
1) Parmi les calculs suivants, déterminer ceux qu’on
Développer les expressions suivantes :
peut effectuer et donner la taille du résultat.
1) (2A + I )( I − A) 3) ( A + 2B)( B − A)
a) AB e) CA i) ABC
2) ( A + 2I )2 4) (2A − B)2
b) A − B f) CB j) A2 !
c) AC g) B + C k) B2 b a
56 Soit X = avec a, b, c et d réels.
d) A + 2C h) BAC l) C2 c d
2) Effectuer les calculs possibles. On souhaite résoudre l’équation X 2 = I.
1) Montrer que, si b = 0, les solutions de l’équation ne
52 Une image numérique en nuances de gris est re-
dépendent que de c.
présentée par une matrice où le coefficient situé dans
2) Montrer que, si b 6= 0, les solutions sont telles que :
la i-ème ligne et la j-ème colonne est égal au niveau de
gris, entre 0 (blanc) et 1 (noir), du pixel correspondant. 1 − a2
c=et d = − a.
b
1 −3 −2
57 Soit la matrice A = −1 1 − 4 .
−1 2 −2
1) Calculer A2 ,
puis vérifier que A3 = 2I.
2) En déduire A3n , A3n+1 et A3n+2 pour tout n ∈ N.
58 Soit la suite un telle que u0 =0 et un+1=un + 2n . 65 ! ALGO
n
1 0 1 1 0 un a b
Soit M la matrice et l’algorithme suivant.
Prouver que, pour n 6= 0, 0 1 0 =0 1 0 .
c d
0 0 2 0 0 2n
1. a, b, c, d, det sont des nombres
59 INFO 2. L1 et L2 sont des listes
À l’aide d’un logiciel de calcul formel, déterminer An 3. Traitement
pour tout n entier naturel non nul. 4. Saisir a, b, c, d
1 −4 −4 1 −3 −2 5. det prend la valeur ad - bc
1) A = −1 1 2 2) A = −3
1 2 6. Si det=0 alors Afficher "Impossible"
1 −2 −3 3 −3 −4 7. Sinon
! 8. L1[1] prend la valeur d/det
cos θ − sin θ
60 On pose A(θ ) = pour θ ∈ R. 9. L1[2] prend la valeur -b/det
sin θ cos θ
10. L2[1] prend la valeur -c/det
1) Démontrer que A(θ ) A(θ ′ ) = A(θ + θ ′ ). 11. L2[2] prend la valeur a/det
2) Démontrer que, pour tout n ∈ N, An (θ ) = A(nθ ). 12. Afficher L1, L2
13. Fin Si
Inverse d’une matrice
1) Préciser la signification de l’affichage « Impossible ».
61 Pour chaque matrice, déterminer si elle est inver- 2) Que dire de la matrice obtenue par l’affichage des
sible et, si oui,
! calculer son inverse. ! listes L1 et L2 ? Vérifier la réponse par un calcul.
−3 2 −3 4 3) Programmer l’algorithme dans AlgoBox et le tester
1) 5)
−2 2 6 −8 pour a = 3, b = 2, c = 2, d = 3.
! !
4 2 −2 −1 4) On suppose que M est inversible.
2) 6)
3 6 −1 −1 Démontrer que MT est inversible et que :
! √ !
8 4 3+1 2 −1 T
3) 7) √ MT = M −1 .
−4 −2 1 3−1
! !
0 2 1 0
4) 8) 5) En déduire comment modifier simplement l’algo-
3 6 −4 −4
rithme pour qu’il calcule, si possible, l’inverse de la
1 −2 −2 transposée de M.
62 Soit la matrice A = −1 0 − 2 .
! !
−1 −2 0 1 1 2 0
66 Soit les matrices A = et B = .
1) Calculer A2 + A. 0 1 1 1
2) En déduire que A est inversible et déterminer A−1 . Pour toute matrice carrée inversible M et tout entier na-
n
turel n, on note M − n = M −1 .
1 −2 −1
1) Démontrer que,!pour tout n ∈ Z :
63 Soit la matrice A = −2 1 .
1 !
n 1 n n 2n 0
−2 2 0 a) A = b) B =
0 1 2n − 1 1
1) Calculer A2 − 3A. 2) Peut-on en déduire ( AB)n pour tout n ∈ Z ?
2) En déduire que A est inversible et déterminer A−1 .
67 Inverse d’un produit
0 −2 −1 Soit A et B deux matrices inversibles et λ ∈ R ∗ .
64 Soit la matrice A = 1 1 .
3 1) Prouver que AB est inversible et déterminer ( AB)−1 .
−1 −2 0 2) Prouver que λA est inversible et déterminer (λA)−1 .
1) Démontrer que 2A − A2
= I.
2) En déduire que A est inversible et calculer A−1 .
Résolution d’un système linéaire 1 −2 −2 1 −2 2
73 Soit A = 2 1 2 et B = 2 5 −6.
2 0 1 −2 −4 5
68 MÉTHODE 3 p. 93
1) Montrer que A et B sont inverses l’une de l’autre.
À l’aide des matrices mais sans l’aide de la calculatrice
2) Résoudre les systèmes d’équations suivants :
ou (
d’un logiciel, résoudre les systèmes
( √ suivants√:
−4x + 3y = 2 3 3x + 3y = 3 x − 2y − 2z = 0
x + 2y − 2z =−2
1) 3) √ a) 2x + y + 2z =−9 b) 2x + 5y − 6z =−7
−x + y = 5 −3x − 3y = 1
( ( 2x + z =−8 −2x − 4y + 5z = 8
9x − 4y = 2 6x + 8y = 8 400 (
2) 4) 2x + 5y = 8
−1, 8x + 0, 8y = −9 x + 1, 5y = 1 450 74 Soit le système linéaire (S) .
3x − 4y = 15
!
69 À l’aide des matrices mais sans l’aide d’un logi- x
ciel, résoudre les systèmes suivants (on discutera des On pose X = et X ′ = x y .
y
solutions
( selon les valeurs de θ) : 1) a) Écrire (S) sous la forme matricielle AX = B.
cos θx − sin θy = cos θ + sin θ b) Vérifier que A est inversible et calculer A−1 .
1)
cos θx + sin θy = − cos θ + sin θ c) En déduire les solutions du système.
√
3 2) a) Écrire (S) sous la forme matricielle X ′ A′ = B′ .
cos θx − sin θy =
2) 2 b) Que peut-on dire de A et A′ ? de B et B′ ?
cos θy + sin θx = − 1 c) Exprimer X ′ en fonction de A et B.
2
75 Soit a et b deux réels.
70 MÉTHODE 4 p. 94 (
4x + 3y
= a
Résoudre chacun des systèmes d’équations suivants 1) Résoudre le système linéaire .
8x + 7y = b
avec la calculatrice ou un logiciel de calcul formel : 2) Déterminer les coordonnées du point d’intersection
3x − 3y − 2z = 0
− x − 3y − 2z = −1
des droites d’équations 12x + 9y = 4 et 8x + 7y = 1
1) 3x + y + z = −2 3) −3x − 2y + 2z = 0 dans un repère donné.
−2x + 3y + 2y = −1 3x + 3y − z = −1
76 Déterminer la fonction polynôme du second de-
2x − 3y + z = −8
−2x − 3y − 2z = 2
gré dont la courbe représentative est la parabole pas-
2) −3x + 2y − 3z = 3 4) −3x − 3y + 2z = 1 sant par les points A(−1 ; −3), B(3 ; −5) et C (4 ; −13).
x − y + z = −1 x + 2y + 3z = −2
77 Soit la fonction polynôme de degré 3 définie par
71 Déterminer, si c’est possible, deux réels a et b f ( x ) = ax3 + bx2 + cx + d représentée ci-dessous.
vérifiant l’égalité
! !donnée. ! ! ! !
5 2 a 4 1 3 a −2 5
1) = 2) =
−1 3 b 9 2 1 b 11 3, 8
81 ALGO 1
−3 6
83 Soit A = 6 −8 12 et I l’identité d’ordre 3.
Soit l’algorithme suivant dans lequel A[i][j] est un
nombre correspond au coefficient aij de la matrice A. 3 −3 4
1) Déterminer les réels a et b tels que aA + bI = A2 .
1. n, p, i, j sont des nombres entiers
2) En déduire que A est inversible et exprimer A−1 en
2. A est une matrice
fonction de A et I.
3. Traitement
4. Pour i allant de 1 à n 84 Soit ABC un triangle tel que [ AB], [ BC ], [ AC ] sont
5. Pour j allant de 1 à p respectivement de longueurs 4 cm, 6 cm, 5 cm et tan-
6. Saisir A[i][j] gents à son cercle inscrit en M, N, P.
7. Fin Pour Le but est de calculer x = AM, y = BN, z = CP.
8. Fin Pour A
bc
9. Pour i allant de 2 à n
P
10. Pour j allant de 2 à p M
bc
bc
11. A[i][j]=A[i-1][j]+A[i][j-1]
12. Fin Pour
13. Fin Pour
B C
bc
bc
bc
14. Afficher la matrice A N
1) Démontrer que le problème revient à résoudre
1) Expliquer à quoi servent les lignes 4 à 8. l’équation matricielle :
2) Quelle matrice s’affiche en sortie si on saisit
1 1 0 x 4
1 3 6 0
1 0 1 y = 5
A = −1 1 2 3 ?
2 4 5 6 0 1 1 z 6
(
3x + 7y = 4 90 ALGO
86 Soit le système .
12x + 28y = 16
Soit la partie traitement d’un algorithme destiné à cal-
1) Sa matrice associée est-elle inversible ?
culer, si possible, le produit C de deux matrices A et B.
2) Déterminer une relation entre les deux équations.
3) En déduire
que les solutions du système sont les 1. Saisir A, B
4 − 3t
couples t ; pour t ∈ R. 2. ....................
7
3. ....................
x+ y− z= 1
4. Si .... alors
87 Soit le système (S) : 2x − 3y + z = −5 . 5. Afficher "Erreur de dimension"
x − 4y + 2z = −6 6. Sinon
1) Sa matrice associée est-elle inversible ? 7. n égale le nombre de .... de A
2) Montrer que la troisième équation est une combinai- 8. m égale le nombre de .... de B
son linéaire des deux ( autres. 9. Pour i allant de 1 à n faire
x+ y− z= 1
3) Montrer que (S) ⇔ . 10. Pour k allant de 1 à m faire
− 5y + 3z = −7
11. ....................
4) En
déduire que les solutions
de (S) sont les triplets
−2 + 2t 7 + 3t 12. Fin Pour
; ; t pour t ∈ R.
5 5 13. Fin Pour
5) Vérifier à l’aide du logiciel Xcas. 14. Fin Si
88 Système paramétré
(
(3 − λ) x − 2y = −4 1) Compléter les lignes 2, 3 et 4 destinées à tester si le
Soit le système où λ ∈ R.
5x − (4 + λ ) y = 5 produit AB est possible ou non.
1) a) Démontrer que, si λ vérifie λ2 + λ − 2 6= 0, alors 2) Exprimer cik en fonction de aij et b jk .
le système admet un unique couple solution. 3) Écrire une procédure qui calcule cik .
b) À l’aide du calcul matriciel, déterminer le couple 4) Compléter l’algorithme et le tester avec un logiciel.
solution du système en fonction de λ. 5) On s’intéresse à la complexité de l’algorithme.
2) a) Résoudre l’équation λ2 + λ − 2 = 0. a) Quel est le nombre de multiplications nécessaires
b) Résoudre le système pour les racines obtenues à au calcul de cik ? Le nombre d’additions ?
la question précédente. b) En déduire le nombre total d’opérations néces-
89 Équation de Pell-Fermat ALGO
saires au calcul de AB.
c) Expliciter le résultat pour deux matrices carrées
Soit l’équation ( E) : x2 − 7y2 = 1 où x et y sont des
d’ordre n.
entiers naturels.
1) a) Exprimer x en fonction de y.
2 −1 3
b) Écrire un algorithme qui, pour y entier de 0 à
91 Soit A = −3 −1 et B = 4A − A2 .
1
1 000, calcule x, teste s’il est entier et affiche les
1 1 1
couples solutions.
c) Le programmer sur la calculatrice ou un logiciel et 1) Calculer B puis AB.
donner les solutions. 2) En déduire que A est inversible et déterminer A−1 .
2) a) Montrer que si ( x ! ; y) est solution 3) Dans un repère orthonormé de l’espace, soit trois
! de ! ( E), alors
x ′ 8 21 x plans et leurs équations :
( x ′ ; y′ ) tel que = l’est aussi.
y′ 3 8 y • P : 2x − y + 3z = 1
b) En déduire un algorithme qui, à partir de la so- • Q : −3x + y − z = 2
lution triviale (1 ; 0), donne de proche en proche • R : x+y+z = 3
9 autres solutions. Déterminer les coordonnées de l’intersection de ces
c) Le programmer et donner les solutions. trois plans à l’aide de la matrice B.
92 Vous avez dit logique ? INFO b) Avec la calculatrice ou un logiciel de calcul formel,
PARTIE A en déduire m, n, p en fonction de a, b, c.
c) Exprimer de même m′ , n′ , p′ avec a′ , b ′ , c′ .
1) Quel nombre prolonge le plus logiquement la série
3) Vérifions les résultats dans CaRMetal.
1, 2, 4, 8 ?
a) Placer trois points A, B et C non alignés, puis le
2) Soit le polynôme f : x 7→ ax3 + bx2 + cx + d tel que
point D d’abscisse x(A)+x(B)-x(C) et d’ordonnée
f (1) = 1, f (2) = 2, f (3) = 4 et f (4) = 8.
y(A)+y(B)-y(C).
a) Identifier f à l’aide d’un logiciel de calcul formel.
b) Que semble-t-on pourvoir dire du point D ?
b) En déduire un nombre qui prolonge la série 1, 2,
c) Définir M, N et P à l’aide de formules similaires
4, 8.
et vérifier qu’ils sont solutions du problème posé.
3) Soit maintenant la série 1, 2, 4, 8, 16 conçue pour être
4) Démontrer que, si quatre points A, B, C, D non ali-
logiquement prolongée par 32.
gnés sont les milieux des côtés d’un quadrilatère
Soit le polynôme g : x 7→ ax4 + bx3 + cx2 + dx + e
MNPQ, alors ABCD est un parallélogramme.
tel que g(1) = 1, g(2) = 2, g(3) = 4, g(4) = 8 et
5) Cherchons par une méthode analytique à déterminer
g(5) = 16.
M, N, P, Q tels que A, B, C, D soient les milieux res-
a) Identifier g à l’aide d’un logiciel de calcul formel.
pectifs de [ MN ], [ NP], [ PQ], [ MQ].
b) En déduire un nombre qui prolonge la série 1, 2,
a) Déterminer R la matrice carrée d’ordre 4 telle que :
4, 8, 16.
PARTIE B a b c d = m n p q R.
P1 P2 P3 P4 T M E
t1 = 1 t2 = 3 t3 = 6 t4 = 10
A 3 2 2 1 P1 10 15 3
B 4 3 0 2 P2 12 8 2
1) a) Exprimer tn en fonction de n. C 0 5 3 2 P3 4 12 4
b) Avec une calculatrice ou un tableur, déterminer P4 3 5 1
deux couples d’entiers ( p ; q ) tels que p2 = tq
et les nombres « carrés triangulaires » correspon- 10 15 3
3 2 2 1 12
dants. 8 2
1) Soit F = 4 3 0 2 et R = 4
.
12 4
c) Vérifier que 41 616 est carré triangulaire. 0 5 3 2
3 5 1
2) a) On pose x = 2q + 1 et y = 2p. Démontrer que a) Calculer le produit P = FR.
p2 = tq si, et seulement si, x2 − 2y2 = 1. b) En déduire le coût de l’énergie nécessaire à la fa-
b) Montrer que, si les entiers naturels x et y vérifient brication d’un article B.
l’égalité 2 2 ′ ′ 1
! x − 2y! = !1, alors x et y définis par 2) Calculer le produit U = P × 1.
x′ 3 4 x
= la vérifient aussi. 1
y′ 2 3 y Donner une interprétation du résultat.
c) Vérifier que si x est impair, alors x ′ l’est aussi.
3) Calculer le produit V = 1 1 1 × P.
d) En déduire un algorithme qui donne 10 nombres Donner une interprétation du résultat.
carrés triangulaires. Le programmer sur un logi- 4) À l’aide d’un produit matriciel, calculer le coût total
ciel et donner ces 10 nombres. pour produire 4 articles A, 3 articles B et 8 articles C.
5) À la fin d’une journée, on a constaté que la fabrica-
a+b 0 b 1 0 1
tion de ces trois articles a coûté 14 800 e en travail,
96 Soit A = b b et J = 1 0 1.
a
18 000 e en matières premières et 4 400 e en énergie.
b 0 a+b 1 0 1
Déterminer le nombre d’articles A, B et C qui ont été
1) Exprimer A en fonction de l’identité I, J, a et b.
fabriqués au cours de cette journée.
2) Calculer J n (on pourra d’abord calculer les premières
puissances de J, émettre une conjecture et la démon-
98 Méthode de Cayley-Hamilton
trer par récurrence). !
a b
3) Calculer A2 . Soit la matrice M = où a, b, c, d sont des réels.
( a + 2b )n − an c d
4) Démontrer l’égalité An = an I + J.
2 1) Démontrer que M2 = ( a + d) M − ( ad − bc) I.
1 0 −1 2) En déduire que si ad − bc 6= 0, alors M est inversible.
5) Soit C = 1 0 −1. Calculer le produit C J.
Retrouver dans ce cas l’inverse de M en fonction de
1 0 −1 a, b, c et d.
6) Démontrer par l’absurde que :
1 2 x 3 a
a) si a = 0, alors A n’est pas inversible.
99 Montrer que l’équation 2 3 4 y = b
b) si a + 2b = 0, alors A n’est pas inversible.
1 b 3 4 5 z c
7) Pour a 6= 0 et a + 2b 6= 0, on pose B = I − J. a des solutions si, et seulement si, les réels a, b, c suivent
a a( a + 2b )
Montrer que B est l’inverse de A. dans cet ordre une progression arithmétique.
100 INFO 2 0 3
103 Soit la matrice A = 0 1 0 et la suite (un )
Avec un logiciel de calcul formel, étudier l’existence de
solutions des systèmes en fonction des paramètres : 0 0 2
définie par u0 = 0 et un+ n
1 = 2u n + 3 ×
2 .
x + y + (1 − m ) z = m + 2
2 n 0 un
1) (1 + m ) x − y + 2z = 0
1) Démontrer que An = 0 1 0 .
2x − my + 3z = m+2
0 0 2n
2
x − my + m z = m
2 0 0 0 0 3
2) mx − m2 y + mz = 1 2) Soit D = 0 1 0 et S = 0 0 0.
− m3 z = − 1
mx + y 0 0 2 0 0 0
x + my + z = 1 a) Vérifier que DS = SD.
3) (m + 1) x + 2y + (m − 3)z = −1 b) Montrer que, pour tout k > 2, on a Sk = 0.
c) Utiliser le formule du binôme de Newton pour
( m − 1) x − 3z = −1
x + y + z + t = a calculer An .
x − y − z + t = b 3) En déduire (un ) sous forme explicite.
4)
− x − y + z + t = c 104 Matrice de Gram
−3x + y − 3z − 7t = d
Dans un repère orthonormé (O ; ~i,~j) du plan, soit ( AB)
ax + by + z = 1
une droite, M un point quelconque du plan et H le pro-
5) x + aby + z = b jeté orthogonal de M sur ( AB).
x + by + az = 1
x y z
1+ a + 1+2a + 1+3a = 1
3
x y A
6) 2+ a + 2+2a + 2+z3a = 1
2
+ 3+y2a + 3+z3a = 1
x
3+ a
H
101 Système non linéaire 1
3 2 6 1
x y z
=
Le but est de résoudre le système x4 y5 z12 = 2 −2 −1 1 2 3 4 5 6 7
2 2 5
x y z = 3 B
−1 M
lorsque x, y, z sont des réels strictement positifs.
−→
1) On pose X = ln x, Y = ln y et Z = ln z. On appelle matrice de Gram, associée aux vecteurs AB
−→ −→ −→ −−→ !
Montrer que la résolution du système revient à −−→ AB · AB AB · AM
et AM, la matrice G = −−→ −→ −−→ −−→ .
déterminer X, Y et Z tels que : AM · AB AM · AM
1) a) Justifier que la distance du point M à la droite
3 2 6 X 0
( AB) est égale à MH. p
4 5 12 Y = ln 2 det( G )
2 2 5 Z ln 3 b) Démontrer que MH = .
AB
2) Soit les points A(−1 ; 3), B(6 ; −1) et M (1 ; −1).
2) À l’aide de la calculatrice, déterminer le triplet solu- a) Déterminer la matrice de Gram associée aux vec-
tion ( X ; Y ; Z ). −→ −−→
teurs AB et AM.
En déduire le triplet ( x ; y ; z) solution du système. b) En déduire la distance de M à ( AB).
102 Matrice nilpotente 105 Matrice idempotente
Une matrice carrée A est dite nilpotente s’il existe un Une matrice carrée A est dite idempotente si A2 = A.
!
entier positif p tel que Ap
= 0. a b
1) Soit une matrice A = .
1) Montrer que si A est nilpotente, alors I − A est inver- c d
sible et préciser son inverse. Traduire par un système que A est idempotente.
2) Montrer que la somme de deux matrices nilpotentes 2) Résoudre ce système en considérant deux cas :
qui commutent est une matrice nilpotente. • b=0 • b 6= 0.
1 0 1 !
1 2 −1
Soit les matrices A = 0 0 et B = .
1
3 0 2
0 1 0
109 Que vaut A + B ?
! 2 2 0
2 2 0
A + B n’existe pas d Aucune des trois pro-
a b 3 1 2 c
3 1 2
0 1 0 positions précédentes
114 Pour tout entier naturel n non nul, on peut écrire An = A + J avec J égale à :
0 0 0 0 0 0 0 n−1 0 0 0 0
a n − 1 0 0 b 0 0 n − 1 c 0 0 0 d 0 0 0
0 0 0 0 0 0 0 0 0 0 n−1 0
120 Si A est une matrice carrée dont le carré est la matrice nulle 0, alors :
a A est inversible b A=0 c A3 = 0 d ( I − A ) −1 = I + A
!
k 0
121 Soit la matrice H = où k ∈ R ∗ et A une matrice carrée d’ordre 2. Alors :
0 −k
a AH = HA b H 2 = k2 I c H 3 = − k3 I d k2 H − 1 = H
122 Un système de Cramer est un système d’équations linéaires dont la matrice des coefficients est inversible.
Parmi
( les systèmes linéaires suivants,
( lesquels sont des systèmes
( de Cramer ? (
x + 3y = 1 6x + 3y = 1 x + 2y = 1 6x + 3y = 1
a b c d
2x − y = 3 4x − 2y = 3 −2x − 4y = 3 4x + 2y = 3
(
5x − 3y = 3
123 Le système a pour solution le couple de réels ( x ; y) tels que :
3x − 2y = 2
! ! ! ! ! ! ! ! ! ! ! !
x 5 −3 3 x −2 3 3 x −2 −3 3 x 2 −3 3
a = b = c = d =
y 3 −2 2 y −3 5 2 y 3 5 2 y 3 −5 2
(
2x + my = 4
124 Pour quelle(s) valeur(s) de m, le système admet-il une unique solution ?
mx + y = 5
√ √
a m=− 2 b m=0 c m= 2 d m=2
A Un peu de réflexions
1 + +
A B
~′ ~j
u ~u
−5 −4 −3 −2 −1 O ~i 1 2 3 4 5
B Ça tourne ! ! !
x x′
Dans le plan complexe, soit deux points M et M′ d’affixes z = x + iy et z′ = x ′ + iy′ .
y y′
Soit la rotation de centre O et d’angle θ qui transforme M en M ′ .
1) Exprimer z′ en fonction de z et θ.
−−→ −−→
2) En déduire les coordonnées de OM ′ en fonction ! de celles
! de OM.
x ′ x
3) Déterminer alors la matrice R telle que ′
=R .
y y
4) Vérifier que la matrice R est inversible et déterminer son inverse.
π
5) a) Pour θ = , calculer R et R −1 .
3
b) À quel angle de rotation est associée la matrice R −1 ? Vérifier avec le logiciel.
• Créer la matrice D. A
2 +
• Placer un point A, puis créer le vecteur ~u
−→
tel que ~u = OA.
~v 1 ~u
• Construire le représentant du vecteur ~v ~j
d’origine O en multipliant la matrice D par
le vecteur ~u. −2 −1 O ~i 1 2
C Application !
5 −3
Soit la matrice M = .
6 −4
1) a) Vérifier la condition établie à la question 3 de la partie B .
b) Calculer les valeurs propres
! de M. On! les note dans l’ordre croissant λ1 et λ2 .
1 1
c) Vérifier que U1 = et U2 = sont des vecteurs propres associés respectivement
2 1
à λ1 et λ2 . ! !
λ1 0 1 1
2) Soit les matrices D = et P = .
0 λ2 2 1
En cryptographie symétrique, le chiffrement de Hill est un système de chiffrement par bloc qui
utilise les propriétés de l’arithmétique modulaire et des matrices. Inventé par Lester S. Hill en
1929, il consiste à substituer les lettres du message clair, non pas l’une après l’autre, mais par
« paquets ». On obtient ainsi un message chiffré plus difficile à casser.
Chaque lettre est codée par son rang diminué de 1 dans l’alphabet latin.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Avant qu’il ne soit traité, on formate d’abord le message clair : on supprime accents, espaces et
ponctuation, on regroupe les lettres par bloc de 2 (si une lettre reste orpheline à la fin, on ajoute
arbitrairement une lettre), puis on remplace chaque lettre par le nombre correspondant dans le
tableau. On forme ainsi une matrice à 2 lignes qu’on !
note X.
D L R 3 11 17
Exemple DE L’OR 7→ 7→ =X
E O A 4 14 0
Ensuite, on calcule AX, où A est une matrice carrée d’ordre 2 fixée, appelée clé du chiffrement.
On obtient une matrice Y où chaque coefficient est remplacé par le plus petit entier naturel qui
lui est congru modulo 26. Enfin, on convertit en lettres grâce au tableau.
!
73
Exemple Appliquons la clé de chiffrement A = .
58
! ! ! !
73 3 11 17 33 119 119 7 15 15 HPP
= 7→ = Y 7→ 7→ HVPLPH
58 4 14 0 47 167 85 21 11 7 V L H
A Késako ?
On souhaite déchiffrer le message KYBNSY qui a été obtenu avec la clé précédente.
1) Déterminer la matrice chiffrée associée à ce message.
D’ordinaire, si A est inversible : AX = Y ⇔ X = A−1Y. Mais ici : AX ≡ Y ⇔ X ≡ A−1Y [26].
Il faut donc inverser A modulo 26 : c’est la clé du déchiffrement.
2) a) Écrire A−1 sous la forme k−1 B avec B à coefficients entiers et k le déterminant de A.
b) Il existe des algorithmes efficaces pour déterminer l’inverse de k modulo n mais pour
n = 26, la « force brute » est sans doute la manière la plus simple. Voici l’algorithme :
C Casser le code
Un agent du KGB a intercepté un bout de message codé par un chiffrement de Hill (FYIR) et sa
transcription en message clair (VLAD). Montrer que cela suffit à retrouver la clé du chiffrement.
Récréation, énigmes
Une matrice magique est une matrice carrée d’ordre n ∈ N ∗ dont les sommes des n coefficients de chaque ligne,
colonne et diagonale sont égales à un même nombre, appelé alors constante magique. Si, en plus, les coefficients
de la matrice sont les entiers de 1 à n2 , alors elle est dite normale.
z z z
a) Réécrire cette matrice en remplaçant les croix maltaises z par des
expressions qui dépendent de a, b, c et d.
b) Montrer que a, b, c et d vérifient un système de deux équations.
c) Résoudre ce système et en déduire une matrice magique normale
d’ordre 3.
4) En 1956, dans les ruines du palais d’Anxi en banlieue de l’actuelle X’ian,
ancienne capitale de la Chine, on a retrouvé une plaque métallique da-
tant de la dynastie Yuan (1271-1368) où figure une grille de 36 cases rem-
plies de chiffres arabes orientaux.
a) Vérifier que la matrice d’ordre 6 correspondant à cette grille est une
matrice magique normale.
b) Vérifier que la matrice d’ordre 4 composée des coefficients encadrés
en rouge est une matrice magique.
Suites de matrices et 2
marches aléatoires
Auto-évaluation
Des ressources numériques pour préparer
le chapitre sur manuel.sesamath.net @
un
1 Soit la suite (un ) telle que un+1 = et u0 = 27. 5 Soit A et B deux événements d’un univers tels
3 3 1 4
1) Exprimer un en fonction de n. que P( A) = , PA ( B) = et PA ( B) = .
5 2 5
2) Montrer que (un ) converge et donner sa limite.
1) Calculer P( B) puis PB ( A).
2 Soit la suite ( an )n>0 telle que an+1 = −3an + 4. 2) Pondérer les arbres de probabilité suivants.
1) Montrer qu’il existe une valeur de a0 pour laquelle B b b
A
( an ) est une suite constante. On note k cette valeur. b b
3 Soit D = 0 2 0 et T = 0 0 6 . A
0 0 0
b
B B b
A
0 0 2
1) a) Avec la calculatrice, calculer D2 et D3 . 6 Le mathématicien Andreï Markov remarqua
b) Conjecturer l’expression de Dn . qu’en moyenne, sur les 20 000 premières lettres d’un
c) Démontrer cette conjecture par récurrence. roman de Pouchkine, une voyelle sur huit suit une
2) Démontrer que Tn
= 0 pour n > 3. voyelle et une consonne sur trois suit une consonne.
√ √ 1) Donner les probabilités qu’une consonne suive une
1+ 5 1− 5
4 Soit a = ,b= et les matrices : voyelle et vice-versa.
2 2
2) Soit ( Xn )n>1 la suite de variables aléatoires valant 0
a b a 0
P = 1 1 et D = 0 b . si la n-ième lettre est une voyelle et 1 sinon.
a) Pour tous i et j valant 0 ou 1, déterminer les
1) Vérifier que P est inversible et calculer P−1 . probabilités P{ Xn = i} ({ Xn+1 = j}).
2) Calculer le produit PDP−1. b) Exprimer P({ Xn+1 = 0}) et P({ Xn+1 = 1}) en
fonction de P({ Xn = 0}) et P({ Xn = 1}).
C’est dans l’idée d’expliquer ce paradoxe, qu’en 1907, les époux Ehrenfest imaginent un mo-
dèle avec deux urnes. Au départ, l’urne A contient n boules numérotées et l’urne B aucune. On
tire alors au hasard un numéro entre 1 et n dans l’urne A ou B et on change d’urne la boule
correspondante. Cette expérience aléatoire est répétée un certain nombre de fois.
Exemple
M11 M12 M13 M14 M15
Si −2 6 x 6 2 et −1 6 y 6 1, la marche aléatoire 1
a 15 états possibles. S’il est en M8 , alors, à l’étape
M6 M7 M8 M9 M10
d’après, il sera en M9 , M13 , M7 ou M3 . S’il est en 0
−2 −1 1 2
M1 , alors, à l’étape d’après, il sera en M2 ou M6 . M1 M2 M3 M4 M5
−1
passage de Mi à M j . −1
M1
2) Soit la matrice ligne Ln de taille 4 dont les coefficients sont, dans l’ordre de gauche à droite,
les probabilités d’être dans les états M1 , M2 , M3 et M4 après n étapes.
On dit que Ln est la répartition de probabilité
de la marche aléatoire à l’étape n.
a) Dans toute la suite, on fixe L0 = 1 0 0 0 . Que représente cette matrice ?
b) Où l’ivrogne a-t-il le plus de chance de se trouver après :
• 1 étape ? • 2 étapes ? • 5 étapes ? • 10 étapes ?
c) Intuitivement, pour n assez grand, où l’ivrogne a-t-il le plus de chance de se trouver ?
Que peut-on alors supposer pour lim ( Ln ) ?
n→+ ∞
1 1 1 1
d) Soit L = . Vérifier que LT = L.
4 4 4 4
On dit que L est la répartition stable de la marche aléatoire.
e) La position initiale de l’ivrogne semble-t-elle avoir une influence sur sa marche aléatoire ?
PREUVE
On démontre cette propriété par récurrence. Voici l’initialisation et l’hérédité :
• D0 = I = diag(1, 1, . . . , 1) = diag(d01 , d02 , . . . , d0p ). Donc la propriété est vraie pour n = 0.
• Supposons que, pour un certain entier naturel n, D n = diag(d1n , d2n , . . . , dnp ).
n n+1
d1 0 . . . 0 d1 0 . . . 0 d1 0 ... 0
. . ..
0 dn . . . .. .
0 d2 . . ..
.
d2n+1 . .
D n+1 = D n D = 2 = 0 .
.
. . .
. . . . . 0 .. . . . . . . 0 ..
. .. ..
..
. . 0
0 . . . 0 dnp 0 . . . 0 dp 0 ... 0 dnp+1
Donc la propriété est héréditaire.
! !
−2 0 (−2)n 0
Exemple Soit D = . Alors Dn = .
0 −1 0 (−1)n
1) M est diagonalisable donc M = PDP−1 . En général, une au moins des matrices P et D est
donnée (la diagonalisation, procédé pour les trouver, est hors programme en Terminale).
2) On démontre par récurrence que M n = PD n P−1 (voir au bas de la page 120).
R EMARQUE : Cette définition prolonge celle de suite numérique. On peut ainsi rencontrer
des suites de matrices définies explicitement ou par récurrence.
! ! !
1 3 5
Exemple Soit (Un ) la suite de matrices colonnes U0 = , U1 = , U2 = , ...
1 2 4
!
2n + 1
Cette suite peut être définie explicitement avec Un = mais aussi par la relation de
2n
! ! !
1 0 2 1
récurrence Un+1 = AUn + B avec A = ,B= et U0 = .
0 2 0 1
2n+1 !
n+1
Exemple Soit (Un ) la suite de matrices colonnes de terme général Un = .
1
!2n
1
2n + 1 2+ n 1 2
On a lim = lim = 2 et lim = 0. Donc lim Un = .
n→+ ∞ n + 1 n→+ ∞ 1 + 1
n
n→+ ∞ 2n n→+ ∞ 0
MÉTHODE 2 Expliciter Un pour (Un ) définie par Un+1 = AUn + B Ex. 23 p. 128
Exercice d’application Soit la suite de matrices colonnes (Un ) définie par Un+1 = AUn + B avec :
! ! !
6 2 0 4
U0 = ,A= et B = .
−1 1 2 −2
!
2n 0
1) Démontrer par récurrence que, pour tout n ∈ N, An = .
n2n−1 2n
2) Déterminer la matrice C telle que : C = AC + B.
3) On pose, pour tout n ∈ N, Vn = Un − C. Montrer que, pour tout n ∈ N, Vn = An × V0 .
4) En déduire une expression Un en fonction de n.
Correction
3. Marche aléatoire
A. Marche aléatoire entre deux états
DÉFINITION : Marche aléatoire entre deux états
Lorsqu’un système n’ayant que deux états possibles évolue par étapes successives aléatoires
et indépendantes, on dit qu’il suit une marche aléatoire entre ses deux états.
Exemple Akwa, un chien ayant une puce, rencontre Bali, un autre chien. Chaque seconde, la
puce reste sur un chien ou va sur l’autre. On a un système à deux états : l’état 1 (la puce est sur
Akwa) et l’état 2 (la puce est sur Bali) dont l’évolution est une marche aléatoire entre ces deux
états.
R EMARQUE : Une matrice de transition est dite stochastique : ses coefficients appartiennent
à l’intervalle [0 ; 1] et la somme des coefficients de chacune de ses lignes est égale à 1.
Exemple Reprenons nos chiens et supposons que chaque seconde : soit la puce va d’Akwa
(état 1) à Bali (état 2) une fois sur cinq, soit elle va de Bali à Akwa deux fois sur trois, soit elle
reste sur le même chien. Alors, la marche aléatoire a pour graphe et matrice de transition :
1/5 !
4/5 1/5
4/5 1 2 1/3 T=
2/3 1/3
2/3
DÉFINITION
Pour n ∈ N , on note :
l’événement An : « le système est dans l’état A à l’étape n » ;
l’événement Bn : « le système est dans l’état B à l’étape n » ;
les probabilités an = P( An ) et bn = P( Bn ) telles que an + bn = 1.
La matrice ligne Mn = an bn est appelée la répartition de probabilité à l’étape n.
PROPRIÉTÉ
Pour tout n ∈ N, on a :
Mn + 1 = Mn T Mn = M0 T n .
1−q
b
Bn+1
!
1−p p
Mn T = a n b n = (1 − p) an + qbn pan + (1 − q )bn = Mn+1 .
q 1−q
On démontre par récurrence que, pour tout n ∈ N, on a Mn = M0 T n .
PROPRIÉTÉ
Avec les notations précédentes, si ( p ; q ) 6= (0 ; 0) et ( p ; q ) 6= (1 ; 1), alors
:
q p
il existe une unique répartition stable de probabilité donnée par M = ;
p+q p+q
la suite ( Mn ) converge vers M, indépendamment de la répartition initiale M0 .
PREUVE !
1− p p
• MT = M donc x y = (1 − p) x + qy px + (1 − q )y = x y .
q 1−q
q
x=
(
x − xp + yq = x p+q
D’où le système qui a pour solution p .
x+y = 1 y=
p+q
• an+1 = (1 − p) an + qbn et bn = 1 − an donc an+1 = (1 − p − q ) an + q.
q
Pour tout entier naturel n, posons un = an − . Alors :
p+q
q q q (1 − p − q )
u n+1 = a n+1 − = (1 − p − q ) a n + q − = (1 − p − q ) a n −
p +q p + q p+q
q
= (1 − p − q ) a n − = (1 − p − q ) u n .
p+q
Donc (un ) est une suite géométrique de raison 1 − p − q et on a un = (1 − p − q )n u0 .
Or, 0 6 p + q 6 2, p + q 6= 0 et p + q 6= 2 donc 0 < p + q < 2.
D’où −2 < − p − q < 0 ⇔ −1 < 1 − p − q < 1. Cela entraîne que lim (1 − p − q )n = 0.
n→+ ∞
q p
La suite (un ) converge donc vers 0. Ainsi, lim an = et lim bn = .
n→+ ∞ p + q n→+ ∞ p + q
q p
On a donc bien lim Mn = M avec M = quelle que soit M0 .
n→+ ∞ p + q p + q
Exercice d’application
Akwa, un chien ayant une puce, rencontre Bali, un chien qui n’en a pas.
Chaque seconde, soit la puce va d’Akwa (état 1) à Bali (état 2) cinq fois sur douze, soit elle va
de Bali à Akwadeux fois
sur cinq, soit elle reste sur le même chien.
On note Mn = an bn la répartition de probabilité au bout de n secondes.
1) Déterminer le graphe et la matrice de transition T associés à cette marche aléatoire.
2) Quelle est la répartition de probabilité au bout de 2 secondes ?
11 2
3) Démontrer que, pour tout n entier naturel, an+1 = an + .
60 5
24 11
4) On pose un = an − . Démontrer que (un ) est une suite géométrique de raison .
49 60
24 25
5) En déduire que lim Mn = M = . Interpréter ce résultat.
n→+ ∞ 49 49
6) Vérifier que M est une répartition stable de probabilité, c’est-à-dire que M = MT.
Correction
R EMARQUE : Pour une marche aléatoire qui comporte trois états ou plus, l’étude asympto-
tique est similaire. La difficulté des calculs croît évidemment avec le nombre d’états et on
aura alors recours à la calculatrice ou à un logiciel de calcul formel.
Activités mentales 1
1 3
3 5
4)
1 Soit a et b deux réels et n un entier naturel. 2 4
1
Déterminer si chaque proposition est vraie ou fausse. 1 5 3 3 3
2 3
! ! 3 7
0 1 n 0 1
1) Soit A = . Pour tout n non nul, A = n .
2 0 2 0
! ! 6 On donne la matrice de transition d’une marche
a 0 an 0
2) Soit A = . Pour tout n, An = . aléatoire. Déterminer, si elle existe, sa répartition stable,
0 b 0 bn
! ! c’est-à-dire la matrice ligne M dont la somme des coef-
0 −1 4n 1 0
3) Soit A = . Pour tout n, A = . ficients est égale à 1 et telle que M = MT.
1 0 0 1 ! !
! ! 0 1 0, 25 0, 75
0 0 0 0 1) T = 2) T =
4) Soit A = . Pour tout n > 2, An = . 1 0 1 0
a 0 0 0
11 MÉTHODE 1 p. 121 16 4 −4 1 0 −1
16 A = −18 −4 5 et P = −2 1 .
1
! !
4 3 3 1
Soit A = et P = . 30 8 −7 2 1 −2
−2 −1 −2 −1
1) Avec la calculatrice :
1) Démontrer que P est inversible −1
! et calculer P . a) déterminer les matrices B = AP et P−1 ;
2 0
2) a) Vérifier que A = P P−1 . b) déterminer la matrice D = P−1 B.
0 1
2) a) Exprimer A en fonction de D.
b) En déduire une expression de An .
! ! b) Exprimer A2 et A3 en fonction de P, D2 , D3 et P−1 .
5 3 1 −1 3) On admet que, pour tout entier naturel non nul n :
12 Soit A = et P = .
−6 −4 −1 2 An = PD n P−1 et D n = diag(0, 1, 4n ).
1) Vérifier que P est inversible et calculer P−1 . Déterminer les coefficients de An en fonction de n.
PDP−1 .
!
2) a) Déterminer la matrice D telle que A = −4 6
17 Soit la matrice M = .
b) Démontrer que, pour tout n ∈ N, An = PD n P−1 . −3 5
c) En déduire une expression de An . 1) Vérifier que M2 = M + 2I.
2) Exprimer M3 et M4 sous la forme αM + βI où α et β
2 2 −1
13 Soit les matrices A = −1 −1
1 ,
sont des réels.
−2 −4 3 3) Soit les suites (un ) et (vn ) définies par u0 = 0 et
1 −3 −2 1 2 −1 v0 = 1 et, pour
(tout entier naturel n :
P = −1 1 1 et Q = −2 −4 1 .
u n+1 = u n + vn
.
−2 −1 0 3 7 −2 vn+1 = 2un
1) Avec la calculatrice, vérifier que Q est l’inverse de P. Démontrer que : M n = un M + vn I.
2) Soit la matrice diagonale D = diag(2, 1, 1). 4) Soit la suite (wn ) définie par wn = un − vn .
a) Établir l’égalité A = PDQ. a) Montrer que (wn ) est géométrique de raison −1.
b) Démontrer que, pour tout n ∈ N, An = PD n Q. b) En déduire une expression de wn en fonction de n.
c) En déduire une expression de An . (−1)n
5) Soit la suite ( xn ) définie par xn = un + .
3
−2 −1 −3 On admet que ( xn ) est géométrique de raison 2.
14 Soit les matrices A = −7
4 − 9 ,
En déduire une expression de xn en fonction de n.
1 1 2 6) Déduire de ce qui précède un et vn en fonction de n.
1 −2 −1 −3 1 −5 7) En déduire alors M n en fonction de n.
P = −1 −1 2 et Q = −1 0 −1.
−1 1 1 −2 1 −3 Suites de matrices
1) Avec la calculatrice, vérifier que Q est l’inverse de P.
2) Démontrer qu’il existe D = diag( a, b, c) avec a, b, c 18 Soit la suite de matrices lignes (Un ) définie par
réels telle que A = PDQ.
1
U0 = −1 1 et, pour tout n ∈ N, Un+1 = Un .
10
3) a) Démontrer que, pour tout n ∈ N, An = PD n Q. 1) Calculer U1 , U2 et U3 .
b) En déduire une expression de An . 2) Déterminer l’expression de Un en fonction de n.
! !
−1 −6 3 2 3) La suite (Un ) converge-t-elle ?
15 Soit A = et P = .
1 4 −1 −1 19 Soit la suite de matrices colonnes (Vn ) de taille 2
1) Démontrer que P est inversible et calculer P−1 . telle que, pour tout n ∈ N, Vn+1 = Vn + R avec :
2) Démontrer que : ! !
! 0 2
α 0 V0 = et R = .
a) il existe α et β réels tels que A = P P−1 ; 1 1
0 β
!
α n 0 1) Calculer V1 , V2 et V3 .
b) pour tout n ∈ N, An = P P−1 .
0 βn 2) Déterminer l’expression de Vn en fonction de n.
3) En déduire une expression de An . 3) La suite (Vn ) converge-t-elle ?
20 Soit les suites réelles (un ) et (vn ) définies par 22 Suite de Fibonacci
u n + vn
! ! u
n+1 = La suite de Fibonacci est définie par u0 = 0, u1 = 1, et,
u0 0 2
= et . pour tout entier naturel n, un+2 = un+1 + un .
v0 1 u n + 2vn
0 1
v
n+1 = 1) Soit les matrices Fn = un un+1 et T = 1
3 ! 1 .
un Montrer que Fn+1 =Fn T, puis que Fn = F0 T n .
Soit la suite de matrices ( Xn ) définie par Xn = . √ √
vn 5−1 − 5−1 .
2) Soit la matrice P =
1 1 2 2
Soit enfin la matrice A définie par
2 2
. a) Déterminer la matrice D telle que T = PDP−1.
1 2 b) En déduire T n en fonction de n.
3 3 3) a) Démontrer que, pour tout n ∈ N, on a :
1) a) Démontrer que, pour tout n ∈ N, Xn+1 = AXn .
b) Démontrer
que, pour tout n ∈ N, Xn= An X0 . " √ !n √ !n #
4 6 1 1 1 1+ 5 1− 5
− un = √ −
5 2 2
2 2
5 5 ′
2) Soit P =
6 6 et P = 1 .
1 u n+1
− b) Démontrer que lim = ϕ où ϕ est le
5 5 2 3
a) Montrer que P et P′ sont inversibles. √un
n→+ ∞
1+ 5
b) Déterminer la matrice diagonale B telle que nombre d’or égal à .
2
P′ BP = A. 4) Soit l’algorithme incomplet suivant.
c) Démontrer que, pour tout n ∈ N, An = P′ Bn P. 1. a PREND_LA_VALEUR 0
3) a) Exprimer Bn en fonction de n.
2. b, c, d PRENNENT_LA_VALEUR 1
b) Démontrer que, pour tout n ∈ N :
3. TANT_QUE (d>0.0001) FAIRE
3 3 1 n
4. a PREND_LA_VALEUR b
5 − 5 6 5. b PREND_LA_VALEUR c
Xn =
3 2 1 n
6. c PREND_LA_VALEUR ...
+
5 5 6 7. d PREND_LA_VALEUR abs((c/b-b/a))
4) En déduire les limites des suites (un ) et (vn ). a) Compléter la ligne 6 afin que l’algorithme calcule
7 3
−
! les termes successifs de la suite de Fibonacci.
10 10 3 1
21 Soit les matrices T = et P = .
1 1 b) Expliquer comment s’arrête la boucle TANT_QUE.
2 1
5 5 c) Programmer l’algorithme et obtenir une valeur
1) a) Montrer que P est inversible et calculer P−1 . approchée du nombre d’or à 10−6 près.
b) Montrer qu’il existe une matrice diagonale D telle
23 MÉTHODE 2 p. 122
que T = PDP−1 .
Soit (Un ) une suite de matrices colonnes telle que, pour
c) Démontrer par récurrence que, pour tout n ∈ N,
tout entier naturel n, Un+1 = AUn + B avec :
T n = PD n P−1 .
d) En déduire une expression de T n . 1 3 2 2
U0 = 2 , A = 0 3 et B = 1
2) Soit les suites réelles ( an ) et (!bn ) définies! par a0 et b0
a n+1 an
et l’égalité matricielle =T . 1) Déterminer une matrice C telle que C = AC + B.
bn+1 bn
2) On pose Vn = Un − C.
a) Démontrer par récurrence que, pour tout n ∈ N :
! ! Montrer que pour tout entier naturel n, Vn+1 = AVn .
an n a0 3) Exprimer Vn en fonction de V0 .
=T
bn b0 4) En déduire que Un = An (U0 − C ) + C.
5) a) Démontrer que, pour
tout entier naturel n:
b) Déterminer une expression des termes généraux n 2n × 3n−1
n
A = 3 .
des suites ( an ) et (bn ). 0 3n
c) En déduire la limite de ces deux suites. b) En déduire une expression de Un pour tout n ∈ N.
24 Soit (Un ) une suite de matrices lignes telle que, 1) Quelle est, à 10−3 près, la probabilité qu’un citadin
pour tout entier naturel n, Un+1 =
! Un A + B avec : choisi au hasard dans la ville vienne du quartier A ?
0 −1
2) a) Établir le graphe qui décrit les flux de populations
U0 = 2 1 , A = et B = 1 2 .
1 1 entre ces deux quartiers.
1) Déterminer la matrice C telle que C = CA + B. b) Exprimer an+1 et bn+1 en fonction de an et bn .
2) On pose Vn = Un − C. c) Déterminer la matrice T telle que Un+1 = TUn .
Montrer que pour tout entier naturel n, Vn+1 = Vn A. 3) Démontrer que, pour tout n ∈ N, Un = T n U0 .
3) Exprimer Vn en fonction de V0 . 4) À l’aide de la calculatrice ou de l’ordinateur, calculer
4) En déduire que Un = (U0 − C ) An + C. U5 , U10 et U20 (arrondir les coefficients à 10−5 près).
5) a) Calculer A2 , puis A3 . En déduire A6 .
En déduire An en fonction du reste de la division 27 MÉTHODE 3 p. 125
euclidienne de n par 6. Soit une marche aléatoire définie par le graphe :
b) Déterminer la matrice U57 . 0,2
2/3
Marches aléatoires entre états
On note par une matrice ligne Pn la répartition de pro-
babilité à la n-ième lettre du livre.
26 Une ville est composée de deux quartiers A et B
1) Déterminer la matrice de transition T telle que
comptant respectivement 251 et 386 citadins.
Pn+1 = Pn T.
Soit an et bn les probabilités qu’un citadin provienne des
2) Déterminer un réel λ et une matrice Q tels que :
quartiers A et B lors de la n-ième année d’étude. !
Pn+1 = λPn + Q.
an
Soit la matrice colonne Un définie par : Un = . 3) Démontrer par récurrence que,
pour tout n ∈ N :
bn
24 24
Chaque année, des citadins déménagent : Pn = λn P0 − Q + Q.
37 37
• 5 % des citadins du quartier A vont au quartier B ; 4) En déduire la répartition des consonnes et des
• 12 % des citadins du quartier B vont au quartier A. voyelles dans le livre entier.
29 Jim était présent pour son premier jour de travail. 31 On lance une pièce équilibrée jusqu’à faire deux
Par la suite, s’il est là un jour, la probabilité qu’il soit là « pile » consécutifs.
le lendemain est de 30 %. S’il s’absente un jour, la pro- 1) Traduire le processus par un graphe probabiliste.
babilité qu’il s’absente le lendemain est de 50 %. 2) Écrire la matrice de transition T associée.
Soit pn et an les probabilités que Jim soit respectivement 3) Démontrer qu’en lançant quatre fois la pièce, la
présent et absent le!
n-ième jour. ! probabilité de succès est égale à 0,5.
pn 1 4) Combien de fois doit-on lancer la pièce pour que
On pose Un = et U0 = .
an 0 cette probabilité soit égale à 0,9 ?
1) Exprimer pn+1 et an+1 en fonction de pn et an .
5) Déterminer la répartition stable de probabilité, c’est-
2) En déduire la matrice carrée A d’ordre 2 telle que
à-dire la matrice ligne M telle que M = MT.
Un+1 = AUn .
6) On admet que la suite des répartitions de probabilité
3) Démontrer que Un = An U0 .
converge vers M. Interpréter cette limite.
4) Démontrer que :
! n !
n 1 5 5 1 −1 7 −5 32 Dans une région impaludée, un individu est soit
A = + .
12 7 7 12 5 −7 5 sain, immunisé (I) ou non immunisé (N), soit malade
5) En déduire l’expression de Un en fonction de n. (M). D’un mois à l’autre, son état varie ainsi :
6) À long terme, quelle est la probabilité de voir Jim à • I demeure avec une probabilité de 0,9 ou passe à N ;
son travail ? • N demeure avec une probabilité de 0,6 ou passe à M ;
• M demeure avec une probabilité de 0,2 ou passe à N.
30 Lors de l’Épiphanie, un boulanger insère dans
chaque galette des Rois une fève naturelle : fève de ca- 1) Réaliser un graphe de cette marche aléatoire.
cao, de tonka ou de Gourgane. On suppose qu’il y a 2) Écrire la matrice de transition A.
autant de chance d’avoir un type de fève ou un autre. 3) On suppose qu’un individu sain est immunisé.
1) Déterminer la probabilité d’avoir deux types de En calculant A2 , déterminer la probabilité que :
fèves différents en achetant deux galettes. a) il soit encore immunisé au bout de deux mois ;
2) Déterminer la probabilité d’avoir les trois types de b) il soit malade au bout de deux mois.
fèves en achetant trois galettes. 4) Selon l’état initial d’un individu, déterminer la
3) On définit une marche aléatoire entre trois états qui probabilité qu’il soit malade au bout de :
correspondent au nombre de types de fèves obte- a) 5 mois b) 9 mois c) 1 an
nus par un client du boulanger. Le graphe pondéré
ci-dessous indique les probabilités de passer d’un 33 On a analysé le cours du dollar : au lendemain
état à un autre après achat d’une galette. d’un jour de hausse, la probabilité qu’il monte est 0,4 et
1/3 2/3 1 qu’il ne varie pas 0,6 ; au lendemain d’un jour sans va-
2/3 1/3 riation, la probabilité qu’il monte est 0,4 et qu’il baisse
1 2 3
0,3 ; au lendemain d’un jour de baisse, la probabilité
a) Écrire la matrice M où mij égale la probabilité de qu’il ne varie pas est 0,4 et qu’il baisse est 0,6.
passer de l’état i à j aprèsachat d’une
galette. 1) Traduire le processus par un graphe probabiliste.
b) Justifier que le produit 1 0 0 M est égal à 2) Écrire la matrice de transition T associée.
la matrice ligne d’éléments les probabilités d’être 3) Un jour donné, le dollar monte. Quelle est la
dans l’état 1, 2 et 3 après l’achat de
deux galettes.
probabilité qu’il ne varie pas sept jours après ?
c) Calculer et interpréter le produit 1 0 0 M2 . 4) Déterminer la répartition stable de probabilité, c’est-
d) Quel calcul matriciel donne la probabilité d’avoir à-dire la matrice ligne M telle que M = MT.
les trois types de fèves en achetant cinq galettes ? 5) On admet que la suite des répartitions de probabilité
Effectuer ce calcul à l’aide de la calculatrice. converge vers M. Interpréter cette limite.
!
400 Soit Xn (respectivement Yn et Zn ) l’événement « la
1) Justifier que X1 = puis calculer X2 .
300 marque X (resp. Y et Z) est utilisée le mois n » et xn sa
2) a) Expliquer pourquoi Xn+1 = AX! n + B. ! probabilité (resp. yn et zn ).
x x 1) a) Exprimer xn+1 en fonction de xn , yn et zn .
b) Pour quels réels x et y a-t-on =A + B?
y y (
! yn+1 = 0, 4xn + 0, 3yn + 0, 2zn
an + 400 On admet que : .
c) Soit Yn = . Prouver que Yn+1 = AYn . zn+1 = 0, 1xn + 0, 2yn + 0, 7zn
bn + 300
b) Exprimer zn en fonction de xn et yn , puis xn+1 et
3) On pose Zn = Y2n .
yn+1 en fonction de xn ! et yn .
a) Démontrer que Zn+1 = A2 Zn .
xn
b) En déduire que Zn+1 = 2Zn . 2) Soit la matrice Un = . On admet que :
yn
c) On admet que cela implique que Y2n = 2n Y0 . ! !
0, 4 0, 4 0, 1
En déduire que Y2n+1 = 2n Y1 puis prouver que : Un+1 = AUn + B où A = et B = .
0, 2 0, 1 0, 2
a2n = 600 × 2n − 400 et a2n+1 = 800 × 2n − 400. !
0, 5
4) Que fait l’algorithme ci-dessous ? Justifier. Au début de l’an 2016, on a U0 = .
0, 3
1. Variables On fait alors tourner l’algorithme suivant :
2. a, p et n sont des entiers naturels 1. Saisir un entier n
3. Traitement 2. i prend la valeur 0
0,4 0,4
4. Saisir p 3. A prend la valeur 0,2 0,1
0,1
5. Si p est pair 4. B prend la valeur 0,2
6. n prend la valeur p/2 0,5
5. U prend la valeur 0,3
7. a prend la valeur 600×2n -400 6. Tant que i < n
8. Sinon 7. U prend la valeur A×U+B
9. n prend la valeur p-1/2 8. i prend la valeur i+1
10. a prend la valeur 800×2n -400 9. Fin de Tant que
11. Fin de Si 10. Afficher U
12. Afficher a
a) Donner les résultats affichés par l’algorithme
5) Le bassin A a une capacité de 10 000 poissons.
lorsque l’utilisateur saisit n = 1 puis n = 3.
Écrire un algorithme qui affiche le nombre d’années
b) Quelle est la probabilité qu’un client utilise la
pendant lesquelles le pisciculteur pourra exploiter le
marque X au mois d’avril 2016 ?
bassin A.
Dans la suite de l’exercice, on cherche à déterminer une
37 D’après Bac (Pondichéry - 2014) expression de Un en fonction de n.
Trois marques X, Y et Z se partagent le marché des petits Soit les matrices I identité d’ordre 2 et N = I − A.
pots pour bébé. On suppose qu’une famille consomme 3) On désigne par C une matrice colonne à deux lignes.
chaque mois une seule de ces marques et que : a) Démontrer que C = AC + B équivaut à NC = B.
• si le mois n elle est fidèle à la marque X, alors le mois b) On admet
que N est inversible et qu’on
a
45 20 17
suivant elle a 40 % de chance de changer pour Y et 23 23 46
− 1
10 % de chance de changer pour Z ; N = 10 30 . En déduire que C = 7 .
!
43 Chaque consommateur d’une population étudiée 1/3−1/3
5) On note P = .
utilise chaque mois une, et une seule, marque de den- 2/3 1/3
trifice parmi Alenfresh, Blanchico et Carivor. a) Calculer D = P−1 AP, puis D n .
b) En déduire An en fonction de n.
Pour un consommateur pris au hasard, on désigne par c) Que peut-on dire des coefficients de la matrice An
An (resp. Bn et Cn ) l’événement : « Alenfresh (resp. lorsque n tend vers +∞ ?
Blanchico et Carivor) est utilisée au cours du n-ième d) Que conclure, à long terme, sur la position des
mois » et par an (resp. bn et cn ) sa probabilité. trois marques de dentifrice sur le marché ?
Au cours du mois d’essai (n = 0), on a observé les va- e) Est-ce cohérent avec les résultats de la partie A ?
leurs initiales : a0 = 0, 1 ; b0 = 0, 2 et c0 = 0, 7.
44 Lors d’une épidémie de grippe A en France, les
autorités sanitaires constatent qu’un individu est soit
Un sondage a déterminé le comportement suivant des
malade, soit immunisé car ayant déjà contracté un vi-
consommateurs qu’on supposera ne pas changer.
rus proche, soit ni malade ni immunisé.
• La probabilité qu’un client d’Alenfresh le mois n uti-
lise Alenfresh (resp. Blanchico ou Carivor) le mois
De plus, d’une semaine à l’autre :
suivant est 0, 4 (resp. 0, 3 et 0, 3).
• une personne malade le reste avec une probabilité de
• La probabilité qu’un acheteur de Blanchico le mois n
0,4 sinon elle guérit et est immunisée ;
utilise Alenfresh (resp. Blanchico ou Carivor) le mois
• une personne immunisée a une probabilité de 0,1 de
suivant est 0, 3 (resp. 0, 4 et 0, 3).
ne plus l’être sans pour autant tomber malade ;
• La probabilité qu’un consommateur de Carivor le
• une personne ni malade ni immunisée tombe malade
mois n utilise Alenfresh (resp. Blanchico ou Carivor)
avec une probabilité de 0,3.
le mois suivant est 0, 2 (resp. 0, 1 et 0, 7).
1. Variables
2. x, y sont des réels
3. i est un entier Königsberg en 1736
4. Traitement
Le problème des sept ponts de Königsberg est un pro-
5. x prend la valeur 1
blème mathématique que Leonhard Euler a résolu en
6. y prend la valeur 1
1736 et qui est connu pour être à l’origine de la théorie
7. Pour i allant de 1 à 5
des graphes. On ne propose pas ici de résoudre ce pro-
8. x prend la valeur x+2y
blème mais de s’intéresser au graphe qui lui est associé.
9. y prend la valeur x+y
10. Afficher la valeur x/y
11. Fin Pour
Le promeneur s’est blessé à la cheville mais suit tou- 2) On décide de séparer chaque type de plantes (par
jours inlassablement une marche aléatoire entre les exemple en utilisant trois serres différentes) pour dé-
quatre zones. Ainsi, toutes les vingt minutes : terminer leur évolution lorsque celles-ci ne sont fer-
• s’il est sur une île, 9 fois sur 10 il y reste, ou alors il tilisées que par des plantes de génotype identique.
change de zone en empruntant un pont au hasard ; On note rn , mn et bn les proportions des individus de
• s’il n’est pas sur une île, 3 fois sur 4 il reste où il est, chaque type, respectivement de génotype AA, Aa et aa
ou alors il va sur une île en empruntant un pont au à la n-ième génération, qui
sont égales initialement.
hasard. Soit Xn la matrice ligne rn mn bn .
1) Vérifier que la matrice de transition est : 3) a) Déterminer la matrice carrée M telle que pour tout
n ∈ N, Xn+1 = AXn .
9/10 1/30 1/30 1/30
1/30 9/10 1/30 1/30 b) Exprimer Xn en fonction de X0 et M.
D= .
1/6 1/12 3/4 0 4) Déterminer les proportions de mufliers de chaque
1/6 1/12 0 3/4 couleur à la quatrième génération.
2) Dans une session du logiciel Xcas
: 2 0 0 1 0 0
a) Saisir les matrices T et P = a b c d . 5) Soit P = 0 2 −1 et D = 0 1
0 .
b) Exécuter les deux instructions : −2 4 0 0 0 0, 5
• S:=P*T=P a) Déterminer P−1 puis vérifier que M = PDP−1.
• resoudre([a+b+c+d=1,S],P) b) Exprimer M n en fonction de n.
Expliquer ce que chacune d’elles produit. c) En déduire X n en fonction de n.
c) Au bout d’une très longue promenade, quelle est 6) Déterminer la limite de X n quand n tend vers ∞ ?
la probabilité de trouver le promeneur sur l’île 1 Peut-on en déduire que la séparation des cultures fa-
sachant qu’il est sur une île ? vorise la diversité biologique ?
!
8 −4 PARTIE C : Modèle d’Usher (1966)
3) Soit la matrice P = .
1 1 En 1972, Usher modélise une population de rorquals
a) Vérifier que P−1 LP est une matrice diagonale D. bleus (une espèce de baleine) structurée en six classes
b) En déduire une expression de Lt en fonction de t. d’âge d’amplitude égale à deux ans, plus une septième
c) Exprimer alors jt , at et nt en fonction de t. classe pour les individus de 12 ans ou plus.
jt a t n
4) Déterminer les limites des quotients , et t+1 . On donne la matrice d’Usher associée à ce modèle :
nt nt nt
En donner une interprétation.
0 0 0, 19 0, 44 0, 5 0, 5 0, 45
0, 87 0 0 0 0 0 0
PARTIE B : Modèle de Lefkovitch (1965) 0 0, 87 0 0 0 0 0
U= 0 0 0, 87 0 0 0 0 .
0 0 0 0, 87 0 0 0
Le modèle de Lefkovitch divise la population en classes
de stade et non plus d’âge comme celui de Leslie. La 0 0 0 0 0, 87 0 0
matrice associée, appelée matrice de Lefkovitch, in- 0 0 0 0 0 0, 87 0, 8
tègre toujours les taux de fécondité et de survie mais
1) Faire le graphe de cycle de vie associé à cette matrice.
aussi les probabilités qu’un individu change de stade.
2) À partir de quel âge ces baleines peuvent mettre bas ?
3) On étudie l’évolution sur 50 ans d’une population
Soit une population d’insectes structurée en trois constituée initialement de 10 baleineaux d’un an.
classes de stade – larves, adultes reproductifs et adultes À l’aide du logiciel de calcul formel Xcas :
non reproductifs – qu’on numérote dans cet ordre et a) Créer la matrice U et la matrice colonne A des ef-
dont on note les effectifs après n semaines respective- fectifs initiaux.
ment xn , yn et zn . Son graphe de cycle de vie associé est : b) Déterminer ce que produit le programme suivant
(touches Shift+Entrée pour aller à la ligne) :
M:=A;
9/4 for(n:=1;n<=50;n++){
M:=border(M,floor(Uˆn*A));}
1 2 3
1/4 1/4 c) Quelle est la répartition des baleines par classes
1/2 1/2 1/4 après 50 ans ?
d) Interpréter le graphique donné par l’instruction :
seq(plotlist(row(M,n),color=n),n=0..6)
1) Écrire la matrice de Lefkovitch L associée au graphe.
2) À l’aide du logiciel de calcul formel Xcas : 175
a) Créer la matrice L. 150
125
b) Exprimer sa puissance n-ième M = Ln avec : 100
M:=matpow(L,n). 75
50
c) En déduire xn , yn et zn en fonction de x0 , y0 et z0 .
25
d) Montrer qu’au fil des semaines, la proportion de
12 5 10 15 20 25 30 35 40 45 50
larves parmi tous les insectes tend vers .
17
! !
1 2 1 −0, 5
Soit P = ,A= et D = P−1 AP trois matrices et n un entier naturel.
1 3 0, 75 −0, 25
50 On a :
! !
0, 5 0 0, 25 0
a D= b D= c A n = P−1 D n P d An = PD n P−1
0 0, 25 0 0, 5
4 3 2 2
1 !
− −
1 2 n 3n 2n 3n .
Soit A = 3
1 et B = . Pour n entier naturel, on donne An = 2
6 6 3 4
−1 − −3 − n+ n − n+ n
6 ! 2 3 2 3 !
an 2
53 Soit (Un ) la suite de matrices de terme général Un = définie par Un+1 = AUn et U0 = .
bn −3
6 5 1
!
0 − n an 2
2n 3 2n − 1
lim Un = b Un = c Un = lim
a d =−
10 9 3
n→+ ∞ 0 n →+ ∞ bn 3
− n − n
3n 2 2 !
5
54 Soit (Un ) la suite de matrices définie par Un+1 = AUn + B et U0 = . Alors Un est égale à :
−8
1 1
1
3 5
1
4 + n−2 + n 4+ n 2 + n−1 − n 2+ n
a
2 3 b
3 c
2 3 d
3
3 2 2 9 10 2
−6 − n −1 − n −6 − n −3 − n + n −3 − n
2 3 3 2 3 3
2 2
57 Après quatre matchs, Saviola a plus de chance de perdre que de gagner le match suivant si :
a elle a gagné le premier match c elle a perdu le premier match
b elle a fait match nul au premier match d elle a fait n’importe quel résultat au premier match
58 On conjecture qu’il est probable qu’au bout d’un nombre de matchs suffisamment important, Saviola :
a perdra 1 fois sur 2 b gagnera 1 fois sur 2 c gagnera 3 fois sur 10 d ne gagnera plus
0, 25 0, 75
Soit une marche aléatoire, sa matrice de transition T = et la suite ( Mn ) de répartitions de
0, 15 0, 85
probabilité entre les deux états.
59 La répartition stable de cette marche aléatoire est la matrice M telle que M = MT. Alors :
a M = 5/6 1/6 b M = 17/22 5/22 c M = 1/6 5/6 d M = 1/2 1/2
5 −5
1 n
+ 1 + 5
60 Par la commande matpow(T,n) sur Xcas, on a obtenu T n = 10 10n
.
6 1 1
− n +1 + 5
10 10n
La suite de répartitions de probabilité de cette marche aléatoire :
a ne converge pas c converge vers une limite qui dépend de M0
b converge indépendamment de M0 d converge vers 5/6 1/6
Soit deux suites (un ) et (vn ) modélisant, en fonction du nombre d’années n, l’évolution des
effectifs de deux populations, constituées respectivement de lièvres des neiges et de lynx.
Des statistiques ont montré que :
• lorsqu’il n’y a pas prédation, le nombre de proies un augmente à taux constant a et le nombre
de prédateurs vn diminue à taux constant c ;
• lorsqu’il y a prédation, le taux d’évolution des proies est diminué en proportion de vn (coef-
ficient de proportionnalité b) et le taux d’évolution des prédateurs est augmenté en propor-
tion de un (coefficient de proportionnalité
d).
u n+1 − u n
= a − bvn
Ainsi, on obtient le système un .
v − vn
n+1
= −c + dun
vn
b b b b
b b
b
b b
b
b b
b b
b b
b
b
b
b b b b b
b b b b
b b
b b b
100
b b b
b b b
b b
b b
b
b b b
b b b b b b
b b b b b
b b b
b b b
b b b b
b b b b
b b b b
b b
b b b b b b b b b
b b b b b
b b b b
b b b
b b b b
Nombre de prédateurs
b b b b b b
b b
b b
b b b b b
b b b b b b b b
b b b b b b b b
b b b b
b b b b
b b b b b
b b b b
b b b b
b b b b b
b b b b b b b b b
b b b b b b b
b b b b b b b b
b b b b b b
b b b b b b b b
b b b b
b b b b b b b
75
b b b b b b b b
b b b b b b b b b
b b b b b b b b b b
b b b b b b
b b b b
b b b b b b b b
b b b b b b
b b b b b b b b b b
b b b b b b b b b b b b b b b b
b
b
b b b b b b b b b b b b b
b b b
b b b b
b b b b
b b b
b
b b
b b b b b b b b b b b b b
b b
b b b b b b b b b b b b
b b b b b
b
b b b b b b b b
b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b
b b
b b b
b b b b b b
b b b b b
b b b b b b b b b b b b b b b
b b b b b b b b
b
b b b b b b
b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b
b b b
b b b b b b
b b b b
b b b b b
b b
b b b b b
b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b
b b b b b b b b b b b b
b b
b
b b b b b
b bb bb b b b b b b b b b b b
b b b b b b b b bb b b b b b b b b b b
b
b b b b b b bb bb b bb b b b b b
b b b b b
b b b b b b b
b b
b b b b b b bb bb b b b b b b b b
b b b b b b b b
b
b
b bb b
b b b
b b b b
b b b
b
b b b b b b b b b b b b
b b
b b b b bb bb
b b
b
b
b b b b b b b b b
b b b b b b b b b b b b b b
b b b b b b b b b b b
b
b b b b b
b b b b b
b bb b b
b
b
b b b b b
b b b b b b b b b b b b
b b b b b
b b b b
b b bb b
b
b
b b
b
b
b b b b
b
b b b b b b b
b
b b bb bb b
b
b b b b b b b b b
b b b b b b b b
b b
b
b
b bb b b
b b b b b b
50
b b
b b b b b b b b b b b
b bb b b
b b
b
b
b b b b b b b b
b b b b b b b b bb b b b b
b b b b b bb b b b b b b
b b b b b b b b b b b b b b
b b b b b b b b b bb b b b b b b b
b b b b b b b bb bb b b b b b b
b b b b b b b b b b b b b
b b b b b b b b bb bb b b
b bb b b
b b b b b b b b b
b bb
bb bb bb b b
b
b
b b b b
b b b
b b b b b b b bb bb bb b b b b b
b b b b b b bb bb b b b b b
b b b b b bb b b b b
b b b b b b b
b b bb b b b b bb b b b b b b b b b
b b b b b
b
b bb bb bb bbb b
b
b
b bb b
b
b
b b b b
b b b b b bb bb bb b b b b b
b b b b b b b b b
b b b bb b bb bb bb
bb b b b b b b b b
b b b b b
b b b b bb b b b b b b b
b
b b b b
bb bb b bb bbb bbbbb bb b b b b b b
b b b b b b
b b b b bb b bb b bb bb b b b b
b b b b b b b
b b b b b b
b b b b bb b b b b b b b b b b b b b b b b b b b
b b b bb bb bb b b b b b b b b b b b b b b b b b b b b b
b b b b
b
b b b b bb bb b b b b b b
b b b b bb b b b b b b b b
b
b
b b b b b b b b b b
b b b b b b b b b b b b b b b b b
b b b
b b b b b bb bb b b b b b b b b b b b b b b b b b b b b b b
b b b b b
b b b b b b b b b b b b b b b b b b
b b b b b b b b b b
b b b b bb b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b
b b b b b b b b b b b b b b b
b b b b b
b b b b b b b b b b b b b b b b b b
b b b
b b b
bb b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b b b b
b b b b b b b b
b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b
b b b b b b b b b b b b b b b
b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b
b b b
b b b b b b b b b b b b b b b
b b b
b b b b b b b b b
b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b
b bb b b b b b b b b b b b b b
b b b b b b b b b b b b
b b b b b b b
25
b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b
b b b b b b b b b
b b b b b b b b b b b
b b b b b b b b b b
b b b b b b b b b b b b b b b b b
b b b b b b b b b b b
b b b b b b b b b b
b b b b b b b b
b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b
b b
b b b b b b
b b b b b b b
b b b b b b b b b
b b b b b b b b b b b
b b b b b b b b
b b b
b b b b b b
b b b b b b b
b b b b b b b b b b b b b b
A Premiers comptages
• Comptage naïf : la pertinence d’une page égale le nombre de liens qui renvoient vers elle.
• Comptage pondéré : on suppose qu’un surfeur suit une marche aléatoire sur le graphe.
S’il est sur une page P, alors il se rend ensuite sur une page liée avec une probabilité égale
1
à où m est le nombre de liens issus de la page P. La pertinence d’une page est alors la
m
somme des probabilités affectées aux liens pointant vers cette page.
B Comptage amélioré
Avec les comptages naïf et pondéré, on se rend compte qu’on peut augmenter artificiellement
la pertinence d’une page en créant des liens superflus.
Pour éviter ce problème, on établit un nouveau comptage : le comptage récursif.
Le surfeur suit toujours une marche aléatoire sur le graphe et on cherche à établir la loi de
probabilité de la position du surfeur sur le graphe après un temps infini.
Soit Un = an bn cn dn en la matrice des probabilités que le surfeur soit sur la page A,
B, C, D et E après le parcours de n pages. La matrice initiale U0 est nulle hormis un coefficient
égal à 1 correspondant à la page par laquelle le surfeur entre sur le site.
an est la probabilité qu’après le parcours de n pages, le surfeur soit sur la page A qui donne
1
accès aux pages B, C et D, donc, à la page suivante, an contribue équitablement pour an aux
3
probabilités bn+1 , cn+1 et dn+1 . À l’inverse, les pages B, C et E renvoient à la page A, et ces
1 1 1
pages émettent respectivement 2, 3 et 2 liens. Par conséquent, an+1 = bn + cn + en .
2 3 2
1) De manière analogue, donner les formules pour bn+1 , cn+1 , dn+1 et en+1.
2) Écrire la matrice carrée M telle que Un+1 = Un × M.
3) En déduire l’expression de Un en fonction de n.
4) Avec un logiciel de calcul formel, déterminer la limite de la suite ( M n ) des puissances de M.
En déduire la limite de la suite (Un ).
5) Le concepteur du site est-il satisfait ?
0, 15
Un+1 = J + 0, 85Un M = Un (0, 3K + 0, 85M )
5
où J est la matrice ligne de taille 5 et K est la matrice carrée d’ordre 5 remplies de 1.
1) Expliquer la formule :
0, 15
Un+1 = J + 0, 85Un M.
5
2) Justifier que :
Un+1 = Un (0, 3K + 0, 85M ) .
1) Quel lien pourrait-on supprimer dans le graphe pour mieux contenter le concepteur du site ?
2) Étudier la pertinence des pages de ce nouveau graphe selon les trois autres comptages et la
satisfaction du concepteur.
a 2 + ( a + 1) 2 = c 2 (∗).
b) Soit la suite (vn ) définie par v0 = 1, v1 = 5 et, pour n > 1, vn+1 − 6vn + vn−1 = 0.
Démontrer que, pour n > 1 :
√ √
2+ 2 √ n 2 − 2 √ n
vn = 3+2 2 + 3−2 2 .
4 4
2) a) Vérifier que, pour n ∈ {1, 2, 3} :
b) Soit la suite (un ) définie par u0 = 0, u1 = 5 et, pour n > 1, un+1 − 6un + un−1 = 2.
Démontrer que, pour n > 1 :
√ √
1+ 2 √ n 1 − 2 √ n 1
un = 3+2 2 + 3−2 2 − .
4 4 2
3) Montrer que, pour tout n > 1, un et vn sont les longueurs du petit côté et de l’hypoténuse
d’un TRPI.
Récréation, énigmes
La fougère de Barnsley est une fractale inventée par le mathématicien britannique Michael Barnsley qui ressemble
à la Doradille noire, une fougère de la famille des Aspleniaceae. C’est un exemple simple d’objet autosimilaire, c’est-
à-dire qui conserve sa forme, quelle que soit l’échelle à laquelle on l’observe. Les travaux de Barnsley ont été une
source d’inspiration pour les artistes désireux de modéliser la nature.
On construit une suite de points de coordonnées ( xn ; yn ), initialement ( x0 ; y0 ) = (0; 0), en itérant des transforma-
tions affines w caractérisées par une formule du même type (voir ci-dessous) selon une répartition de probabilité.
La première construit la tige, la troisième et la quatrième construisent les folioles des deux plus grandes feuilles,
respectivement celle de gauche et celle de droite, et la quatrième construit les folioles des autres feuilles. Dans son
livre Fractals Everywhere, Barnsley fournit les coefficients des matrices et les probabilités p ci-dessous. En jouant sur
ces coefficients, on peut imiter d’autres fougères.
w a b c d e f p
xn+1 a b xn e 1 0 0 0 0,16 0 0 0,01
= +
yn+1 c d yn f 2 0,85 0,04 −0, 04 0,85 0 1,60 0,85
| {z } | {z }
A B 3 0,20 −0, 26 0,23 0,22 0 1,60 0,07
4 −0, 15 0,28 0,26 0,24 0 0,44 0,07
A Fonctions arithmétiques
ENT (n) Renvoie la partie entière du nombre n
MOD (n ; d) Renvoie le reste de la division euclidienne de n par d
PGCD (a ; b) Renvoie le PGCD de a et de b
CAR(n) Renvoie le caractère spécifié par le code ASCII du numéro n
CODE (Texte) Renvoie le numéro de code ASCII du premier caractère du texte saisi
Exemples :
On a saisi la formule =PGCD(A6;A7)
dans la cellule B7 qui renvoie 6.
B Matrices
Lorsqu’on travaille avec des matrices dans une feuille de calcul, on valide en tapant :
Ctrl + Maj + Entrée.
147
Fiche 2 Utiliser une calculatrice Casio
X,θ ,T (A).
Déterminer la puissance n-ième d’une matrice, son inverse ou calculer le produit de deux
matrices
Utiliser les touches ∧ pour calculer la puissance, x-1 pour obtenir l’inverse ou × pour la
multiplication.
148
Fiche 3 Utiliser une calculatrice TI
Déterminer la puissance n-ième d’une matrice, son inverse ou calculer le produit de deux
matrices
Utiliser les touches ∧ pour calculer la puissance, x-1 pour obtenir l’inverse ou × pour la
multiplication.
149
Fiche 4 Utiliser un logiciel de calcul formel
Exemples :
• Pour trouver un couple solution à l’équation : 17x − 40y = 1, on écrit iabcuv(17,-40,1)
qui renvoie [−7 ; −3].
• Pour convertir le nombre 496 en base 7, on écrit convert496,(base,7) qui renvoie [6,0,3,1]
7
pour 1306 .
• Pour trouver le code ASCII du mot "merci", on écrit asc("merci") qui renvoie [109,101,114,99,105].
1 2 −2 1
• Pour trouver l’inverse de la matrice B= , on écrit inv(B) qui renvoie 3 .
3 4 2 − 12
150
SOLUTIONS
Chapitre AR1 S’entraîner
Multiples. Division euclidienne. Congruence 1 D150 = {1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150}
10 1) a est pair.
(−2)19 = −(25 )3 × 24 ≡ 16 ≡ 5 (11)
12 6 ≡ 1 (5) donc 6n − 1 ≡ 0 (5) donc 6n − 1 est
2) a est impair.
divisible par 5.
3) Un entier et son carré ont même parité.
SOLUTIONS 151
13 1) ( x + y)( x − y = 21 donc Chapitre AR2
PGCD. Théorèmes de Bézout et de Gauss
x + y = 21 x+y = 7
ou Auto-évaluation
x−y = 1 x−y = 3
26 2
1 1) PGCD(26, 65) = 13 d’où = .
Les couples sont (11; 10) et (5; 2). 65 5
72 4
x = 17 2) PGCD(72, 54) = 18 d’où = .
54 3
2) x ( x − 7y) = 17 donc
x − 7y = 1 255 51
3) PGCD(255, 35) = 5 d’où = .
35 7
Système impossible, pas de solution entière.
2 16, 32 et 40.
20 n = 4r + r = 5r avec 0 6 r < 5
3 1) 9 et 16 sont premiers entre eux.
n ∈ {0, 5, 10, 15, 20}
2) 35 et 91 ne sont pas premiers entre eux.
26 • 351 = 7 × 50 + 1 et 85 = 7 × 12 + 1
35 = 5 × 7 et 91 = 7 × 13.
35112 × 8515 ≡ 112 × 115 ≡ 1 (7)
3) 31 et 67 sont premiers entre eux. En outre, ils
Le reste de la division par 7 est 1.
sont tous les deux premiers.
• 16 = 7 × 2 + 2 et 23 = 7 × 3 + 2
1612 − 2312 ≡ 212 − 212 ≡ 0 (7) 4 1) Fausse. 36 est divisible par 6 et 9 mais pas par
Le reste de la division par 7 est 0. 54.
2) Vraie car 8 et 9 sont premiers entre eux.
29 25 = 26 − 1 donc 25 ≡ −1 (13). 3) Vraie car 36 est le plus petit multiple commun à
54k − 1 ≡ (52 )2k − 1 ≡ (−1)2k − 1 ≡ 1 − 1 ≡ 0 (13) 4 et 18.
Donc 54k − 1 est divisible par 13. 4) Fausse car 30 est un multiple de 10 et 15 et
31 30 ≡ 1(11) ; 31 ≡ 3(11) ; 32 ≡ 9(11) ; 33 ≡ 5(11) ; 30 6≡ 0 (150)
34 ≡ 4(11) ; 35 ≡ 1(11).
Le cycle est de 5. On peut remplir le tableau de 5 1) Vraie car si x est multiple de 81, il est aussi
congruence suivant : multiple de 9.
n ≡ ( 5) 0 1 2 3 4 2) Vraie car (1 ; 1) est un couple solution de
n
3 ≡ (11) 1 3 9 5 4 l’équation.
3n − 7 ≡ (11) 8 10 5 1 0
1) Les restes possibles de la division de 3n par 11
6 1) (3 ; 2) 3) (1 ; 0)
sont : 1,3,4,5 et 9.
2) (−1 ; 1) 4) (−3 ; −2)
2) 3n − 7 est divisible par 11 si n ≡ 4 (5).
2 PGCD(35, 42) = 7 et 35 = 7 × 5, 42 = 7 × 6.
Lorsque le coureur A aura fait 6 tours, le coureur B
aura fait 5 tours, soit un temps de 35 × 6 = 210 s.
152 SOLUTIONS
3 1) PGCD(24 ; 40) = 8. Le côté du carré doit 6 1) 4 divise 5( x + 3). Or PGCD(4, 5) = 1, donc
diviser 24 et 40, donc le plus grand côté possible d’après le théorème de Gauss, 4 divise ( x + 3).
est de 8 cm. On a donc x + 3 = 4k.
2) 40 = 8 × 5 et 24 = 8 × 3 En remplaçant dans l’équation,
on obtient y = 5k.
Pour former le plus petit carré, il faut mettre 3 fois x = −3 + 4k
Les couples solutions sont : ,k ∈ Z
la longueur et 5 fois la largeur du rectangle, soit y = 5k
120 cm. 2) 41x = 9(−y) (1)
9 divise 41x. Or PGCD(9, 41) = 1, donc d’après le
4 1) PGCD(78; 108) = 6 car
théorème de Gauss, 9 divise x.
108 = 78 × 1 + 30
On a donc x = 9k.
78 = 30 × 2 + 18 En remplaçant dans l’équation, on obtient
30 = 18 × 1 + 12 y = −41k.
x = 9k
18 = 12 × 1 + 6
Les couples solutions sont : , k∈Z
y = −41k
12 = 6 × 2
2) PGCD(144; 840) = 24 car
840 = 144 × 5 + 120 7 (−2 ; 3) est solution.
8 1) Oui car PGCD(37 ; 25) = 1, donc d’après le
144 = 120 × 1 + 24
théorème de Bézout, il existe au moins un couple
120 = 24 × 5
solution.
3) PGCD(202; 138) = 2 car 2) Non car PGCD(51 ; 39) = 3 et comme 1 n’est
202 = 138 × 1 + 64 pas multiple de 3, d’après le corollaire de Bézout,
138 = 64 × 2 + 10 il n’y a pas de solution.
64 = 10 × 6 + 4 3) Oui car PGCD(51 ; 39) = 3 et comme 2016 est
divisible par 3, d’après le corollaire du Bézout, il
10 = 4 × 2 + 2
existe des solutions entières.
4 = 2×2
13 1) PGCD(441 ; 777) = 21 car
5 (−1)n + 1(n + 1) = 1. Donc d’après le théorème 777 = 441 × 1 + 336
de Bézout, n et (n + 1) sont premiers entre eux.
441 = 336 × 1 + 105
336 = 105 × 3 + 21
105 = 21 × 5
2) PGCD(9185 ; 2004) = 167 car
9185 = 2004 × 4 + 1169
2004 = 1169 × 1 + 835
1169 = 835 × 1 + 334
835 = 334 × 2 + 167
334 = 167 × 2
SOLUTIONS 153
28 On utilise l’algorithme d’Euclide : Chapitre AR3
40 = 17 × 2 + 6 ( 1) Les nombres premiers
17 = 6 × 2 + 5 ( 2) Auto-évaluation
6 = 5×1+1 ( 3) 1 Ils ne comptent aucun diviseur autre que 1 et
eux-même.
40 et 17 sont donc premiers entre eux.
2 1) divisible par 3 5) divisible par 11
On remonte l’algorithme d’Euclide : 2) divisible par 7 6) divisible par 7
de (3), on obtient 5 = 6 − 1 3) divisible par 11 7) divisible par 11
On remplace dans (2) : 4) divisible par 5 8) divisible par 3
17 = 6 × 3 − 1 donc 6 × 3 = 17 + 1
3 1) 1, 2, 4, 8, 16
On multiplie (1) par 3 2) 1, 3, 5, 15
40 × 3 = 17 × 6 + 6 × 3
3) 1, 2, 3, 4, 6, 8, 12, 24
= 17 × 6 + 17 + 1 4) 1, 2, 3, 4, 6, 9, 12, 18, 36
= 17 × 7 + 1 5) 1, 3, 5, 9, 15, 45
6) 1, 3, 17, 51
On a alors 17 × (−7) − 40 × (−3) = 1.
7) 1, 3, 7, 9, 21, 63
42 • (2 ; 2) est une solution particulière.
8) 1, 7, 13, 91
• Soit ( x ; y) la solution générale, on écrit :
4x − 3y = 2 4 1) n ≡ 0 (6) 3) n ≡ 0 (12)
4( 2) − 3( 2) = 2 2) n ≡ 0 (15) 4) n ≡ 0 (72)
154 SOLUTIONS
√
6 13 • 9 < 97 < 10.
30 = 2 × 3 × 5 120 = 23 × 3 × 5 On teste tous les nombres premiers inférieurs à 10
40 = 23 × 5 800 = 25 × 52 soit : 2, 3, 5 et 7. Ils ne divisent pas 97.
64 = 26 2 000 = 24 × 53 97 est un nombre premier.
70 = 2 × 5 × 7 60 000 = 25 × 3 × 54 √
• 10 < 109 < 11
On teste tous les nombres premiers inférieurs à 11,
7 6! = 2 × 3 × 22 × 5 × 2 × 3 = 24 × 32 × 5
soit 2, 3, 5, 7. Ils ne divisent pas 109.
8 292 − 4 = (29 − 2)(29 + 2) = 27 × 31 = 33 × 31
109 est premier.
852 − 16 = (85 − 4)(85 + 4) = 81 × 89 = 34 × 89
• 117 est divisible par 3 car : 1 + 1 + 7 = 9.
9 48 = 24 × 3 donc 48 a 5 × 2 = 10 diviseurs.
117 n’est pas premier.
10 60 = 22 × 3 × 5 donc 60 a 3 × 2 × 2 = 12
√
diviseurs. • 16 < 271 < 17.
11 Il faut utiliser les diviseurs premiers les plus petits On teste tous les nombres premiers inférieurs à 17,
possibles avec la puissance la plus grande soit : 2, 3, 5, 7, 11, 13. Ils ne divisent pas 271.
possible : 271 est un nombre premier.
• avec 1 diviseur premier : 25 = 32, soit 6 √
• 17 < 323 < 18.
diviseurs.
On teste tous les nombres premiers inférieurs à 18,
• avec 2 diviseurs premiers : 24 × 3 = 48, soit
soit : 2, 3, 5, 7, 11, 13, 17.
5 × 2 = 10 diviseurs.
17 divise 323 car 323 = 17 × 19.
• avec 3 diviseurs premiers : 2 × 3 × 5 = 30, soit
323 n’est pas un nombre premier.
2 × 2 × 2 = 8 diviseurs. √
Le nombre qui possède le plus de diviseurs et qui • 20 < 401 < 21.
est compris entre 2 et 50 est 48. On teste tous les nombres premiers inférieurs à 21,
12 On utilise la même méthode que dans soit : 2, 3, 5, 7, 11, 13, 17, 19. Ils ne divisent pas 401.
l’exercice 11 401 est un nombre premier.
• Avec 1 diviseur premier : 26 = 64, soit 7 √
• 22 < 527 < 23.
diviseurs.
On teste tous les nombres premiers inférieurs à 23,
• Avec 2 diviseurs premiers :
soit : 2, 3, 5, 7, 11, 13, 17, 19.
1) 25 × 3 = 96, soit 6 × 2 = 12 diviseurs.
17 divise 527 car 527 = 17 × 31.
2) 23 × 32 = 72, soit 4 × 3 = 12 diviseurs.
527 n’est pas un nombre premier.
• Avec 3 diviseurs premiers : √
1) 22 × 3 × 5 = 60, soit 3 × 2 × 2 = 12 diviseurs. • 26 < 719 < 27.
2) 2 × 32 × 5 = 90, soit 2 × 3 × 2 = 12 diviseurs. On teste les nombres premiers inférieurs à 27,
Les nombres qui possèdent le plus de diviseurs soit : 2, 3, 5, 7, 11, 13, 17, 19, 23.
sont donc 60, 72, 90 et 96. Ils ne divisent pas 719.
719 est un nombre premier.
25 960 = 26 × 3 × 5.
960 a 7 × 2 × 2 = 28 diviseurs.
SOLUTIONS 155
27 1) 2 650 = 1 272 × 2 + 106 et 1 272 = 106 × 12 Chapitre MS1
donc PGCD(2 650; 1 272) = 106. Matrices : opérations
6 1) F 2) F
156 SOLUTIONS
7 1) 3 × 3 3) n’existe pas Chapitre MS2
2) 3 × 1 4) 1 × 3 Suites de matrices et marches aléatoires
Auto-évaluation
n
8 Les matrices suivantes existent : 1) si det(C ) 6= 0.
1 1) u n = 13 × 27.
3) pour toute condition. n
1 1
4) pour toute condition. 2) 0 < 3 < 1 donc un converge et lim 3 =0
n→+ ∞
5) pour toute condition. donc lim un = 0.
n→+ ∞
7) si C a autant de colonnes que N a de lignes.
8) si N a autant de colonnes que C a de lignes. 2 1) k = 1.
2) bn+1 = −3bn donc (bn ) est géométrique de
9 1) a13 = 18 et a31 = 12. raison −3.
2) a) 68 b) 3 c) 7 3) an = (−3)n ( a0 − 1) + 1.
!
10 1) 5 1 0 0
3 1) D2 = 0 2 0 .
2) Le nombre de T-shirts T2 ; le nombre de T-shirts
0 0 4
de taille L. 1 √ 0 0
D 3 = 0 2 2 0 .
8 −4 4
0 0 8
6
1 √0 0
30 1) 3) 2 −1 1
−13 2) D n = 0 ( 2)n 0 .
4 −2 2
0 0 2n
−4
4 −3 3) Initialisation : D0 = I3 .
2) 4) −2
−8 3 Hérédité : D n+1 = Dn D
−7
1 √0 0 1 √0 0
= 0 ( 2) n 0 0 2 0
2n
−1 0 0 −1 0 0 0 0 2
37 1) ;
0 −1 1 0 1 √0 0
−2 6
−8 0
= 0 ( 2) n + 1 0 .
2) ; 0 0 2n + 1
−2 −2 0 −8
3
4) T = 0 et, par récurrence, T n = 0 pour n > 3.
−1 −4 −9 −11
3) ;
8 7 22 13 √
1 −1
1 0
4 1) det( P) = a − b = 5 6= 0.
4) ;
3 −2 0 1 P est donc√inversible.
√ !
5 − 5+5
P−1 = 5√
5
√10
5+ 5
.
68 1) (13 ; 18) 3) ∅ − 5 10
1 1
2) ∅ 4) (1 000 ; 300) 2) PDP−1 = .
1 0
Auto-évaluation QCM
109 c 110 a 111 d
112 b 113 b c 114 c
115 b 116 c 117 d
118 c 119 b c 120 c d
121 b d 122 a b 123 d
124 b d
SOLUTIONS 157
6 1) 2 fois sur 3 une consonne suit une voyelle et 7 −0, 5
23 1) .
fois sur 8 une voyelle suit une consonne. −0, 5
2) Vn+1 = Un+1 − C = AUn + B − C =
2) a) P{ Xn =0} ({ Xn+1 = 1}) = 23 .
AUn + B − AC − B = AVn .
P{ Xn =1} ({ Xn+1 = 1}) = 13 .
3) Vn est donc une suite géométrique, d’où :
P{ Xn =1} ({ Xn+1 = 0}) = 78 .
Vn = An V0 .
P{ Xn =0} ({ Xn+1 = 0}) = 18 .
4) Un = Vn − C = An (U0 − C ) + C.
b) P{ Xn+1 =0} et P{ Xn+1 =1} valent respectivement :
1 5) a) Preuve par récurrence.
8 P{ Xn =0} + 23 P{ Xn =1} et 78 P{ Xn =0} + 13 P{ Xn =1} .
Initialisation : triviale.
Hérédité n+1 = A × A n
S’entraîner n+1 : A
3 2( n + 1) × 3n
1 1) Fausse 3) Vraie = .
0 3n + 1
n+1
2) Vraie 4) Vraie 3 n − 1
+ 5n × 3 − 0, 5
b) 2 .
5 × 3n
2 1) Oui 2) Non − 0, 5
2
158 SOLUTIONS
LEXIQUE
A Matrice inverse ..................................... Page 91
Matrice ligne ............ ............................ Page 87
AT ............ ........................................... Page 88
Matrice nulle ............ ............................ Page 89
A−1 ............ ......................................... Page 91
Matrices égales ............ ........................ Page 87
Antisymétrique ..................................... Page 96
Matrice transposée ............................... Page 88
B Multiple ............ ..................................... Page 9
Base ............ ........................................ Page 24 N
C Nilpotente ............ .............................. Page 107
Chiffrement ............ .............................. Page 29 Nombre composé ................................. Page 55
Chiffrement affine ............ .................... Page 29 Nombre premier ............ ....................... Page 55
Coder ................................................... Page 29 Nombres de Fermat .............................. Page 68
Coefficient (matrice) ............................. Page 87 Nombres de Mersenne .......................... Page 63
Congru (nombre congru modulo n) ............ Numéro ISBN ............ ............................ Page 8
............................................................. Page 12
Corollaire de Bézout ............................. Page 35 O
Corollaire de Gauss .............................. Page 36 Opposée (matrice) ................................ Page 88
Crible d’Ératosthène ............................. Page 57 Ordre (matrice carrée) ............ .............. Page 87
Critère d’arrêt ....................................... Page 55
P
D
Performance d’un algorithme ............ ... Page 47
Déchiffrement ............ .......................... Page 29 PGCD ............................................. Pages 27, 31
Déterminant ............ ............................. Page 92 Plus grand commun diviseur ................ Page 31
diag(a1 , a2 , . . . , an ) ............................. Page 87
Principe de descente infinie ............ ...... Page 9
Diagonale principale ............................. Page 87
Principe des tiroirs ............ .................... Page 9
Différence (matrices) ............ ................ Page 88
Principe du bon ordre ............................ Page 9
Diviseur ............ .................................... Page 9
Produit d’une matrice par un réel ............
E ............................................................. Page 89
M S
Matrice ................................................. Page 87 Somme (matrices) ............ .................... Page 88
Matrice carrée ............ .......................... Page 87 Stochastique ...................................... Page 123
Matrice colonne .................................... Page 87 Symétrique ........................................... Page 96
Matrice diagonale ................................. Page 87 Système cryptographique RSA ............
Matrice identité d’ordre n ............ ......... Page 88 ............................................................. Page 72
LEXIQUE 159
T Théorème fondamental de l’arithmétique
............................................................. Page 58
Tableau de congruence ............ ........ Pages 6, 15
Transitivité ............ ............................... Page 13
Taille (matrice) ............ ......................... Page 87
Triplets pythagoriciens ......................... Page 64
Théorème de Bézout ............ ................ Page 34
Théorème de Gauss ............ ................. Page 35
Crédits photographiques
p. 20 : © Alain Laurent/Wikimediacommons ;
p. 26h : © Santeri Viinamäki/Wikimediacommons ;
p. 26b : © Jared Tarbell/Wikimediacommons ;
p. 33 : © Rémi Jouan/Wikimediacommons ;
p. 48 : dessin de Jules Maurice Gaspard (1862-1919)/Wikimediacommons ;
p. 50 : © Wongkarwai88/Wikimediacommons ;
p. 71 : Gravure du XIXe siècle, anonyme/Wikimediacommons ;
p. 74 : © Alexander Klink/Wikimediacommons ;
p. 83 : Albrecht Dürer (1471-1528)/Wikimediacommons ;
p. 114 : © BabelStone/ Wikimediacommons ;
p. 137 : © JLPC/ Wikimediacommons.
160 LEXIQUE