Algèbre 2 Chapitre 1 : Arithmétique dans Z PDF

Module : Algèbre 2 Chapitre 1 : Arithmétique dans Z Prof. Omar Kchit Licence d’Éducation Sciences Mathématiques 2024/2025 Table des matières 1 Division euclidienne dans Z...

Module : Algèbre 2 Chapitre 1 : Arithmétique dans Z Prof. Omar Kchit Licence d’Éducation Sciences Mathématiques 2024/2025 Table des matières 1 Division euclidienne dans Z 2 2 Divisibilité dans Z 2 3 PGCD et PPCM 3 3.1 Le plus grand diviseur commun (PGCD).................. 3 3.2 Le plus petit commun multiple (PPCM).................. 5 3.3 Théorèmes fondamentaux.......................... 6 4 Algorithme d’Euclide 7 4.1 Calcul du plus grand commun diviseur................... 7 4.2 Résolution de l’équation diophantienne ax + by = c............ 7 5 Systèmes de numérations 9 1 1 Division euclidienne dans Z Division euclidienne dans Z Théorème (Propriété fondamentale de N) Toute partie non vide A de N admet un plus petit élément. Théorème Soit (a, b) ∈ Z × Z∗. Alors il existe un couple unique (q, r) ∈ Z2 vérifiant : a = qb + r et 0 ≤ r < |b|. Définition 1. La procédure de calcul du couple (q, r) est appelée la division euclidienne de a par b. 2. Les entiers relatifs q et r sont appelés respectivement le quotient et le reste de la division euclidienne de a par b. De plus, a est appelé dividende et b est appelé diviseur. 2 Divisibilité dans Z Définition Soient a ∈ Z et b ∈ Z∗. 1. On dit que b divise a (ou que a est divisible par b) s’il existe un entier c ∈ Z tel que a = bc. Dans ce cas, on note b | a. Dans le cas contraire, on dit que b ne divise pas a (ou que a n’est pas divisible par b) et on note b ∤ a. 2. Si b | a, on dit aussi que b est un diviseur de a et que a est un multiple de b. 3. L’ensemble des diviseurs de a est noté D(a). Remarque Soient a et b deux entiers relatifs non nuls. 1. Tous les diviseurs positifs de a sont inférieurs a. 2. b divise a ⇐⇒ −b divise a. 3. L’ensemble D(a) des diviseurs de a est fini. 4. D(a) = D(|a|). 2  5. |a| = |b| ⇐⇒ a | b et b | a. 6. b | a ⇐⇒ a ∈ bZ = {kb tel que k ∈ Z}. Proposition Soient a, b, d, m et n des entiers relatifs non nuls. 1. Si d | n et d | m, alors d | (am + bn). 2. Si d | n, alors ad | an. 3. Si ad | an, alors d | n. n 4. Si d | n, alors | n. d 3 PGCD et PPCM Définition 1. Soient a et b deux entiers relatifs. On appelle diviseur commun de a et b tout entier relatif d tel que d | a et d | b. Autrement dit, tout élément de D(a) ∩ D(b). Si au moins l’un des entiers relatifs a et b est non nul, alors il existe seulement un nombre fini de diviseurs communs. 2. Soient a1 , a2 ,... , an des entiers relatifs. On appelle diviseur commun de a1 , a2 ,... , an tout élément de D(a1 ) ∩ · · · ∩ D(an ). 3.1 Le plus grand diviseur commun (PGCD) Définition 1. Soient a et b deux entiers relatifs non tous nuls. On appelle plus grand diviseur commun de a et b le plus grand nombre dans l’ensemble des diviseurs communs de a et b. Il est noté pgcd(a, b) ou a ∧ b. 2. Soient a1 , a2 ,... , an des entiers relatifs non tous nuls. On appelle plus grand divi- seur commun de a1 , a2 ,... , an le plus grand nombre dans l’ensemble des diviseurs communs de a1 , a2 ,... , an. Il est noté pgcd(a1 , a2 ,... , an ) ou a1 ∧ · · · ∧ an. Remarque 1. Un entier relatif d est le plus grand diviseur commun de a et b si et seulement si les trois assertions suivantes sont vérifiées : 3  (a) d ≥ 1. (b) d est un diviseur commun de a et b. Autrement dit, d ∈ D(a) ∩ D(b). (c) Tout diviseur commun de a et b divise d. Autrement dit, ∀c ∈ D(a)∩D(b), c | d. 2. pgcd(a, b) = pgcd(b, a). 3. pgcd(a, b) ≥ 1 et pgcd(b, 0) = |b| si b ̸= 0. 4. Comme 0 a une infinité de diviseurs, alors pgcd(0, 0) n’est pas défini (sauf que dans certaines situations, il est convenable de choisir pgcd(0, 0) = 0). Définition 1. Soient a et b deux entiers. On dit que a et b sont premiers entre eux si pgcd(a, b) = 1. 2. Soient a1 , a2 ,... , an des entiers. On dit que a1 , a2 ,... , an sont premiers entre eux si pgcd(a1 , a2 ,... , an ) = 1. 3. Soient a1 , a2 ,... , an des entiers. On dit que a1 , a2 ,... , an sont deux-à-deux pre- miers entre eux si pgcd(ai , aj ) = 1 pour tout i ̸= j. Remarque 1. 1 est premier avec lui-même et c’est le seul entier naturel qui vérifie cette propriété. 2. a | b ⇐⇒ pgcd(a, b) = |a|. En particulier, ∀k ∈ Z, pgcd(a, ka) = |a|. Théorème Soient a et b deux entiers relatifs non tous nuls. Alors pgcd(a, b) = min{ax + by tel que x, y ∈ Z et ax + by > 0}. C’est-à-dire pgcd(a, b) = min{ax + by tel que x, y ∈ Z} ∩ N∗. Corollaire Soient a et b deux entiers relatifs non tous nuls. Alors, il existe (x, y) ∈ Z2 tel que pgcd(a, b) = ax + by. 4 Autre définition du PGCD Remarque Soient a et b deux entiers relatifs non tous nuls. 1. pgcd(a, b) = ax+by, pour certains entiers x et y, implique directement que tout mul- tiple de pgcd(a, b) est une combinaison linéaire de a et b. C’est-à-dire aZ+ bZ ⊆ pgcd(a, b)Z. 2. Si c est un entier relatifs qui est de la forme c = ax + by pour certains entiers relatifs x et y, alors pgcd(a, b) divise c. Donc, nous avons la relation impor- tante suivante que certaines références l’adoptent comme définition du PGCD : pgcd(a, b)Z = aZ + bZ. De plus, il est facile de voir que pgcd(a, b) est l’unique entier naturel qui vérifie cette relation. 3.2 Le plus petit commun multiple (PPCM) Le plus petit commun multiple (PPCM) Définition 1. Soient a et b deux entiers relatifs non tous nuls. On appelle plus petit commun multiple de a et b le plus petit entier naturel x tel que a | x et b | x. Il est noté ppcm(a, b) ou a ∨ b. 2. Soient a1 , a2 ,... , an des entiers relatifs non nuls. Le plus petit commun multiple de a1 , a2 ,... , an est le plus petit entier naturel x tel que ai | x, pour tout i = 1,... , n. Il est noté ppcm(a1 , a2 ,... , an ). Exemples 1. ppcm(6, 4) = 12. 2. ppcm(7, 3) = 21. 3. ppcm(9, 6, 4) = 36. Autre définition du PPCM Certaines références adoptent la définition suivante du PPCM : Définition Soient a et b deux entiers relatifs non tous nuls. On appelle le plus petit multiple commun de a et b l’unique entier naturel m tel que aZ ∩ bZ = mZ. 5 3.3 Théorèmes fondamentaux Théorème de Bézout Soient a et b deux entiers relatifs non tous nuls. Alors a et b sont premiers entre eux ⇐⇒ ∃ (u, v) ∈ Z2 tel que au + bv = 1. Exemple Pour a = 17 et b = 31, nous avons 17 × 11 + 31 × (−16) = 1. Alors 17 et 1 sont premiers entre eux. Attention ! ! ! Si on remplace 1 par un autre entier d ≥ 2, on aura pas l’équivalence. Par exemple pgcd(2, 3) = 1 et −4 · 2 + 4 · 3 = 4. Exercice Soit n un entier relatif. Montrer que 2n + 1 et 9n + 4 sont premiers entre eux. Théorème de Gauss Soient a, b et c trois entiers relatifs. Si a | bc et pgcd(a, b) = 1, alors a | c. Exemple Pour a = 2, b = 3 et c = 6. Nous avons a = 2 divise bc = 12. Puisque pgcd(a, b) = 1, alors a = 2 divise c = 6. Exercice Trouver tous les entiers relatifs x et y tels que 5(x − 1) = 7y. Corollaire 1. Si a est premier avec c et b est premier avec c, alors ab est premier avec c. C’est-à- dire pgcd(a, c) = 1 et pgcd(b, c) = 1 =⇒ pgcd(ab, c) = 1. 2. ∀k ∈ Z, nous avons pgcd(ka, kb) = |k|pgcd(a, b). ! a b pgcd(a, b) 3. Si k | a et k | b, alors pgcd , =. k k |k| 4. Pour tous entiers relatifs non nuls a et b, nous avons ! a b pgcd , = 1. pgcd(a, b) pgcd(a, b) 6 4 Algorithme d’Euclide 4.1 Calcul du plus grand commun diviseur Algorithme d’Euclide : Calcul du plus grand commun diviseur Proposition Soient a, b et x des entiers relatifs. Alors pgcd(a, b) = pgcd(a + bx, b) = pgcd(b, a + bx). Remarque Soient a et b deux entiers relatifs non nuls. Comme pgcd(a, b) = pgcd(|a|, |b|) et pgcd(a, a) = pgcd(a, 0) = |a|, alors on peut supposer que a et b sont strictement positifs et différents. Lemme (Algorithme d’Euclide) Soient a et b deux entiers strictement positifs. Par la division euclidienne, il existe (q, r) ∈ Z2 tel que a = bq + r. Alors pgcd(a, b) = pgcd(r, b). Algorithme d’Euclide On répète les divisions euclidienne et à chaque fois le diviseur devient le dividende et le reste devient le diviseur. On arrête lorsque on obtient 0 comme reste. Le pgcd(a, b) est donc le dernier reste non nul. Exemple Calculons pgcd(1648, 120) et pgcd(1542, 58). Exercice Déterminer pgcd(255, 141) et trouver les entiers relatifs x et y tels que pgcd(255, 141) = 255x + 141y. 4.2 Résolution de l’équation diophantienne ax + by = c Algorithme d’Euclide : Résolution de l’équation diophantienne ax + by = c Proposition Soient a, b et c trois entiers relatifs non nuls. Alors, l’équation diophantienne ax + by = c admet des solutions si et seulement si pgcd(a, b) divise c. Proposition 7 Soient a, b et c trois entiers relatifs non nuls. Supposons que pgcd(a, b) divise c. Alors, l’ensemble des solutions de l’équation diophantienne (E) : ax + by = c est S = {(x0 + kb0 , y0 − ka0 ); k ∈ Z}, a b avec a0 = , b0 = et (x0 , y0 ) est une solution particulière de l’équation pgcd(a, b) pgcd(a, b) (E). Comment résoudre une équation diophantienne ax + by = c Soient a, b et c des entiers relatifs non nuls et (E) : ax + by = c. Si pgcd(a, b) ne divise pas c, alors S = ∅. Donc, supposons que pgcd(a, b) divise c. 1. En utilisant l’algorithme d’Euclide, on trouve une solution (x0 , y0 ) de ax + by = d où d = pgcd(a, b). c 2. Donc ax0 + by0 = d. Multipliant par c0 = , on trouve ac0 x0 + bc0 y0 = c. Par suite, d (x1 , y1 ) = (c0 x0 , c0 y0 ) est une solution particulière de ax + by = c. 3. Soit maintenant (x, y) une solution de l’équation (E). Alors ax + by = c et ax1 + by1 = c. Par soustraction et simplification par d on trouve a0 (x − x1 ) = −b0 (y − y1 ). Comme pgcd(a0 , b0 ) = 1, par le théorème de Gauss, b0 divise (x − x1 ) et a0 divise (y − y1 ) ; il existe (k, h) ∈ Z2 tel que x = x1 + b0 k et y = y1 + a0 h. En remplaçant dans l’égalité a0 (x − x1 ) = −b0 (y − y1 ), on trouve k = −h. Par suite, la solution générale de l’équation (E) est donnée par S = {(x1 + b0 k, y1 − a0 k) | k ∈ Z}. Exemples Trouver l’ensemble des solutions des équations diophantiennes suivantes : 1. 31x + 12y = 3. 2. 42x + 45y = 4. 3. 255x + 141y = 6. 4. 6x + 15y = 18. 8 5 Systèmes de numérations Systèmes de numérations Depuis bien longtemps, nous écrivons les entiers en base 10 : il y a dix symboles (0, 1, 2,... , 9) appelés chiffres et chaque nombre s’écrit avec un chiffre des unités, un chiffre des dizaines, des centaines,.... Nous allons étudier cette façon d’écrire les entiers et la généraliser à d’autres bases. La base 2 est utilisée au cœur des ordinateurs : il y a alors deux symboles 0 et 1, correspondant à deux états électriques possibles : tension nulle / non nulle aux bornes d’un composant. Proposition Soit b un entier supérieur ou égal à 2. Pour tout entier naturel n, il existe un entier k ≥ 0 et des entiers c0 ,... , ck ∈ {0,... , b − 1} tels que l’on ait n = ck bk + ck−1 bk−1 + · · · + c1 b + c0. On peut en outre imposer les conditions k = 0 si n = 0 et ck ̸= 0 si n ̸= 0. Elles déterminent alors les entiers k et c0 ,... , ck de manière unique. 9