Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algèbre 1 1 ARITHMÉTIQUE DANS Z ATIAMPO KODJO ARMAND@ UVCI 2017 1.0 Table des m

Algèbre 1 1 ARITHMÉTIQUE DANS Z ATIAMPO KODJO ARMAND@ UVCI 2017 1.0 Table des matières 3 4 Objectifs À la fin de cette leçon, vous serez capable : • Comprendre l'arithmétique des nombres entiers notamment la division euclidienne ; • Manipuler les notions de PGCD, de PPCM et de nombre premier • Résoudre les équations algébriques. 5 Introduction Cette leçon présente les concepts de base de l'arithmétique et va nous permettre d'illustrer les raisonnements présentés des précédentes leçons. Les notions présentées trouvent leur usage dans la résolution d'équation et dans la conception d'algorithme de calcul. 7 I - Division Euclidienne I Objectifs A la fin de ceste section , l’étudiant sera capable de :  Identifier les nombres premiers  Manipuler la division euclidienne dan Z Il s'agit de formaliser avec précision la bonne vieille division euclidienne, celle que vous connaissez depuis l'école primaire. A. Divisibilité On appelle entier (ou entier relatif, c'est-à-dire positif ou négatif) tout élément de Z = { . . . , −3, −2, −1, 0, 1, 2, 3,....} Soient d et n des entiers naturels. On dit que d divise n et on note d|n si k N, n ∃ ∈ = dk. On dit aussi que d est un diviseur de n et que n est un multiple de d. Exemple 6= 2×3. on en déduit que 2 divise 6(resp. 3 divise 6) et 6 est un multiple de 2 (resp. de 3) On appelle nombre premier tout nombre entier naturel ayant exactement deux diviseurs : 1 et lui-même. Exemple 2, 3, 5, 7, 11, ... sont des nombres premiers car ils n'ont aucun diviseur à part eux- mêmes et 1 9 Attention 1 n'est pas un nombre premier Définition Soient a et b des entiers naturels avec b ≠ 0. Il existe un unique couple d'entiers (n, r) N × N ∈ tel que a = nb + r et 0 ≤ r < b. Cette égalité est appelée division euclidienne de a par b ; n est le quotient de la division et r en est le reste. Définition On dit que deux entiers naturels a et b sont premiers entre eux s'ils n'ont aucun diviseur commun hormis 1 : d N, (d|a et d|b) = d = 1. ∀∈ ⇒ Exemple Les entiers 14 et 15 sont premiers entre eux. En effet l'ensemble des diviseurs de 14 est l'ensemble A={-14, -7, -2, 1, 2, 7, 14}. L'ensemble des diviseurs de l'entier 15 est B={-15, -5, -3, 1, 3, 5, 15}. Comme on le voit 15 ni 15 ne sont des nombres premiers mais ils sonr premiers entre eux car leur seul diviseur commun est 1 B. Exercice [Solution n°1 p 27] Parmi les assertions suivantes , lesquelles sont vérifiées ? -3 est un nombre premier Un nombre premier est un nombre impair L'ensemble des diviseurs de 3 est {-3, -1, 3, 1} L'ensemble des nombres premiers est un ensemble fini Les entiers 14 et 35 sont premiers entre eux Soient a et b deux entiers premiers entre eux alors a ou b est un nombre premier Division Euclidienne 10 C. Exercice [Solution n°2 p 27] Parmi les assertions suivantes , lesquelles sont vérifiées La relation "divise" n'est pas une relation d'ordre dans Z La relation "divise" est une relation d'ordre dans N La relation "divise " est transitive dans Z Aucune des affirmations précédentes n'est vraie Division Euclidienne 11 II - PGCD, PPCM II Objectifs A la fin de cette section, l’étudiant sera capable de :  Identifier le pgcd de deux nombres entiers  Identifier le ppcm de deux nombres entiers  Manipuler l'identité de Bézout Dans cette section, nous allons étudier les propriétés élémentaires des nombres entiers qui nous serviront de base pour la résolution d'équations algébrique. Nous n'allons pas effectuer les démonstrations des théorèmes , mais le lecteur curieux est invité à chercher à les faire pour mieux appréhender les contours et améliorer la maîtrise des concepts étudies dans les chapitres précédents A. PGCD et PPCM Définition On appelle plus grand commun diviseur (PGCD) de deux entiers a et b le plus grand nombre entier naturel qui divise à la fois a et b : d = PGCD(a, b) si d|a et d|b et ( d' N, d'|a et d'|b = d'|d). ∀ ∈ ⇒ Définition Soit a ≥ 1 et b ≥ 1 deux entiers. Alors il existe un unique entier m ≥ 1 tel que pour tout entier c ≥ 1, c est un multiple de a et de b si et seulement si c est un multiple de m. m est alors le plus petit commun multiple des entiers a et b. On le note m=PPCM(a,b) Fondamental: Identité de Bézout Soient a et b deux entiers naturels premiers entre eux. Alors il existe des entiers relatifs u et v tels que au + bv = 1. 13 Il existe une version forte de ce résultat qui le généralise au cas où les nombres ne sont pas premiers entre eux Fondamental a N, b N, u Z, v Z, au + bv = PGCD(a, b). ∀∈ ∀∈ ∃ ∈ ∃ ∈ L'algorithme d'Euclide permet de déterminer ce PGCD et de trouver des coefficients u et v vérifiant l'égalité de Bézout et sa version forte. Complément : Lemme d'Euclide Soit p un nombre premier et soient a, b N. Si p divise le produit ab, alors p divise a ∈ ou p divise b : p P, (a, b) N × N, p|ab = p|a ou p|b. ∀∈ ∀ ∈ ⇒ Méthode Programme de calcul des coefficients u et v de l'identité de Bézout Début du programme * pgcd (a, 0) = a. * Soit r le reste de la division euclidienne de a par b. Les diviseurs communs de a et b sont les diviseurs communs de b et r. D'où : pgcd (a, b) = pgcd (b, r). Fin du programme Exemple Calculons le pgcd de 137 et 24 . En appliquant le lemme d'Euclide , nous avons (1) 137 = 5 × 24 + 17 pgcd(137, 24) = pgcd(24, 17) (2) 24 = 1 × 17 + 7 pgcd(24, 17) = pgcd(17, 7) (3) 17 = 2 × 7 + 3 pgcd(17, 7) = pgcd(7, 3) (4) 7 = 2 × 3 + 1 pgcd(7, 3) = pgcd(3, 1) (5) 3 = 3 × 1 + 0 pgcd(3, 1) = pgcd(1, 0) = 1 Donc pgcd(137, 24) = 1. Ces calculs permettent ensuite sans mal de reconstituer une identité de Bézout. – La dernière division avec un reste non nul est (4) qui donne 1 = 7 − 2 × 3. On va repêcher une expression de 3 comme un reste dans la relation précédente, soit (3), ce qui donne 3 = 17 − 2 × 7. – On reporte cette expression de 3 donc 1 = 7 − 2 × (17 − 2 × 7). – On regroupe les termes en 17 et 7 donc 1 = −2 × 17 + 5 × 7. – On va repêcher une expression de 7 comme un reste dans la relation précédente, soit (2), ce qui donne 7 = 24 − 1 × 17. – On reporte cette expression de 7 donc 1 = −2 × 17 + 5 × (24 − 1 × 17). – On regroupe les termes en 24 et 17 donc 1 = 5 × 24 − 7 × 17. – On va repêcher une expression de 17 comme un reste dans la relation précédente, soit (1), ce qui donne 17 = 137 − 5 × 24. – On reporte cette expression de 17 donc 1 = 5 × 24 − 7 × (137 − 5 × 24). – On regroupe les termes en 137 et 24 donc 1 = −7 × 137 + 40 × 24. PGCD, PPCM 14 Exemple On va déterminer le pgcd de 141 et 24 A partir du lemme d'Euclide , nous avons les calculs suivants Voici les divisions euclidiennes successives et leurs conséquences en termes de pgcd. (1) 141 = 5 × 24 + 21 , pgcd (141, 24) = pgcd (24, 21) (2) 24 = 1 × 21 + 3 , pgcd (24, 21) = pgcd (21, 3) (3) 21 = 7 × 3 + 0 , pgcd(21, 3) = pgcd(3, 0) = 3 Donc pgcd (141, 24) = 3 et on vérifiera que ces calculs permettent de reconstituer l'identité de Bézout −141 + 6 × 24 = 3. Conseil : On part de l'équation (2) et on remonte à l'expression (1) pour trouver la dernière égalité Fondamental: Lemme de Gauss Soit a, b et c trois entiers strictement positifs. Si a divise le produit bc et si a est premier avec c, alors a divise b. Fondamental: Théorème fondamental de l'arithmétique Tout nombre entier naturel non nul se décompose en un produit fini de nombres premiers : Cette décomposition est unique à l'ordre des facteurs près est l’ensemble des nombres premiers Fondamental Soient m uploads/Philosophie/ cours-de-mathematique-analyse-dans-z.pdf