arithmetique

COURS DE SPÉCIALITÉ MATHÉMATIQUES Terminale S Valère B ONNET ([email protected]) 1er novembre 2006 Lycée P ONTUS DE T YARD 13 rue des Gaillardons 71100 CHALON SUR SAÔNE Tél. : (33) 03 85 46 85 40 Fax : (33) 03 85 46 85 59 FRANCE Site web : http ://www.mathsaulycee.info 2 Lycée Pontus de Tyard 708-709 Table des matières Table des matières I 3 Arithmétique I.1 Les ensembles N et Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.1.1 L'ensemble N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.1.2 L'ensemble Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.1.3 Numération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.1.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.2 Multiples et diviseurs d'un entier relatif . . . . . . . . . . . . . . . . . . I.2.1 Multiples d'un entier relatif . . . . . . . . . . . . . . . . . . . . . . I.2.2 Diviseurs d'un entier relatif . . . . . . . . . . . . . . . . . . . . . . I.2.3 Ensemble des diviseurs d'un entier relatif . . . . . . . . . . . . . I.2.4 Exercices résolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.2.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.3 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.3.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.3.2 Décomposition en produit de facteurs premiers . . . . . . . . . I.4 PPCM et PGCD de deux entiers relatifs . . . . . . . . . . . . . . . . . . . I.4.1 PPCM de deux entiers relatifs . . . . . . . . . . . . . . . . . . . . I.4.2 PGCD de deux entiers relatifs . . . . . . . . . . . . . . . . . . . . I.4.3 Déterminations du PGCD et du PPCM de deux entiers naturels I.4.4 Nombres premiers entre eux . . . . . . . . . . . . . . . . . . . . . I.4.5 Équations diophantiennes . . . . . . . . . . . . . . . . . . . . . . I.4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.5 Congruence modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.5.1 Définition et propriétés immédiates . . . . . . . . . . . . . . . . I.5.2 Petit théorème de F ERMAT . . . . . . . . . . . . . . . . . . . . . . I.5.3 Résolution d'équations avec congruences . . . . . . . . . . . . . I.5.4 Utilisations des congruences . . . . . . . . . . . . . . . . . . . . . I.5.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.6 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.6.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.6.2 Décomposition en produit de facteurs premiers . . . . . . . . . Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 6 9 11 11 11 13 13 14 15 15 15 17 19 19 20 22 24 26 27 28 28 30 31 35 41 41 41 44 46 3 4 Lycée Pontus de Tyard Table des matières 708-709 Chapitre I Arithmétique L'arithmétique est un des secteurs scientifiques les plus anciens et les plus féconds. Fondée essentiellement par les pythagoriciens pour qui tout était nombre, elle connu de grands progrès sous l'impulsion de F ERMAT, E ULER, L AGRANGE, G AUSS et L EGENDRE. Longtemps considérée comme la branche la plus abstraite et la moins utile des mathématiques, elle connaît aujourd'hui de nombreuses applications en informatique, en électronique et en cryptographie. I.1 Les ensembles N et Z I.1.1 L'ensemble N N désigne l'ensemble des entiers naturels et N? désigne l'ensemble des entiers naturels non nuls. On a : N = {0; 1; 2; 3; . . .; n ; n + 1; . . .} et N? = N \ {0}. I.1.1.a Addition et multiplication dans N N est muni de deux opérations : Addition dans N Multiplication dans N - l'addition, notée + ; a +0 = 0+a = a a ×1 = 1×a = a - la multiplication, notée ×. Pour tous entiers naturels a et b , a + b et 0 est élément neutre pour + 1 est élément neutre pour × (a × b ) × c = a × (b × c ) a × b sont des entiers naturels ; on dit que (a + b ) + c = a + (b + c ) + est associative × est associative l'addition et la multiplication dans N sont a +b = b +a a ×b = b ×a des lois de composition internes. + est commutative × est commutative Les principales propriétés de l'addition a × (b + c ) = a × b + a × c et de la multiplication dans N sont résu× est distributive par rapport à + mées dans le tableau ci-contre où a , b et c a + b = 0 ==> a = b = 0 a × b = 1 ==> a = b = 1 désignent des entiers naturels. Remarque Lorsqu'il n'y a pas d'ambiguïté le produit a × b est noté : ab . I.1.1.b Ordre dans N On définit dans N une relation, notée , par : ?(a ; b ) ? N2 , (a b <=> ?c ? N, b = a + c ). Cette relation possède les propriétés suivantes, dont la démonstration est immédiate. 5 6 T HÉORÈME I.1.1 Pour tous entiers naturels a , b et c , on a : (1) aa La relation (2) si (a b ) et (b a ), alors a = b La relation (3) si (a b ) et (b c ), alors (a c ) La relation I. Arithmétique est réflexive. est antisymétrique. est transitive. Remarques 1. Une relation binaire à la fois réflexive, antisymétrique et transitive est une relation d'ordre. 2. Deux entiers naturels a et b sont toujours comparables, c'est-à-dire on a toujours (a b ) ou (b a ), on dit que dans N est une relation d'ordre total. 3. Une relation d'ordre partiel est une relation d'ordre non total. Par exemple ? sur P(N) est une relation d'ordre partiel. On admet le théorème suivant. T HÉORÈME I.1.2 Toute partie non vide de N admet un plus petit élément. Exemples 1. Le plus petit élément de N est 0. 2. Le plus petit élément de l'ensemble {2n + 7n ? N} est 7. I.1.2 L'ensemble Z Z désigne l'ensemble des entiers relatifs et Z? l'ensemble des entiers relatifs non nuls. On a : Z = {. . . ; n - 1 ; n ; . . .; -2 ; -1 ; 0 ; 1 ; 2 ; . . .} et Z? = Z \ {0}. I.1.2.a Addition dans Z L'ensemble Z muni de l'addition possède les propriétés suivantes. T HÉORÈME I.1.3 Pour tous entiers relatifs a , b et c , on a : (1) a + b ? Z. L'addition dans Z est une loi de composition interne. (2) (a + b ) + c = a + (b + c ). L'addition dans Z est associative. (3) a + 0 = 0 + a = a. 0 est élément neutre pour l'addition dans Z. ? ? ? (4) ?a ? Z, a + a = a + a = 0. Tout élément de Z a un opposé dans Z. Remarque Un entier relatif a n'admet qu'un seul opposé, on le note (-a ). Vocabulaire Pour résumer ses propriétés, on dit que (Z, +) est un groupe. Plus généralement, un ensemble muni d'une loi de composition interne est un groupe lorsque : - la loi est associative ; - l'ensemble possède un élément neutre pour cette loi ; - tout élément de cet ensemble admet un « symétrique « dans cet ensemble. Remarque Soit I l'ensemble des isométries du plan. (I, o) est un groupe ; en effet : - la composée de deux isométries est une isométrie ; - la composée des isométries est associative ; - l'application identique (élément neutre pour o) est une isométrie ; - la réciproque d'une isométrie est une isométrie. Lycée Pontus de Tyard 708-709 I.1. Les ensembles N et Z T HÉORÈME I.1.4 Pour tous entiers relatifs a et b , on a : a + b = b + a . 7 L'addition dans Z est commutative. On dit que (Z, +) est un groupe commutatif (ou abélien). Remarques 1. (R, +) et (R? , ×) sont des groupes commutatifs. 2. Le groupe (I, o) est non commutatif. T HÉORÈME I.1.5 Pour tous entiers relatifs a , b et c on a : si a + b = a + c , alors b = c . Démonstration En effet, si a + b = a + c , alors : (-a ) + a + b = (-a ) + a + c ; donc : b = c . I.1.2.b Multiplication dans Z L'ensemble Z muni de la multiplication possède les propriétés suivantes. T HÉORÈME I.1.6 Pour tous entiers relatifs a , b et c on a : (1) a ×b ? Z La multiplication dans Z est une loi de composition interne. (2) a ×b = b ×a La multiplication dans Z est commutative. (3) (a × b ) × c = a × (b × c ) La multiplication dans Z est associative. (4) a ×1 = 1×a = a 1 est élément neutre pour la multiplication dans Z. (5) a × (b + c ) = a × b + a × c La multiplication dans Z est distributive par rapport à l'addition. (Z, +) est un groupe commutatif ; de plus × est une loi de composition interne à Z, associative, distributive par rapport à + et présente un élément neutre, 1, on dit que (Z, +, ×) est un anneau. De plus × est commutative dans Z, on dit que (Z, +, ×) est un anneau commutatif. T HÉORÈME I.1.7 Pour tous entiers relatifs a , b et c , on a : (1) b ×0 = 0; (2) si ab = 0 alors a = 0 ou b = 0. Démonstration Nous ne démontrerons que la première propriété. On a : bb + b × 0 = b (b + 0) = bb = bb + 0 ; donc : b × 0 = 0. Remarques 1. Plus généralement un produit d'entier est nul si et seulement si l'un au moins des en tiers est nul. 2. On déduit de (2) que si ab = ac et a 0, alors b = c . I.1.2.c Ordre dans Z Pour tous nombres entiers relatifs a et b , on pose : b - a = b + (-a ). On définit dans Z une relation, notée , par : ?(a , b ) ? Z2 , a b <==> b - a ? N . Cette relation est une relation d'ordre total. On admet les deux théorèmes suivants. 2006-2007 8 I. Arithmétique T HÉORÈME I.1.8 Soit a et b deux entiers relatifs. (1) Pour tout entier relatif c , on a : a b <==> a + c b + c . (2) Pour tout entier naturel non nul c , on a : a b <==> ac bc . Remarque Lorsqu'on multiplie chaque membre d'une inégalité par un nombre strictement négatif, l'inégalité change de sens. T HÉORÈME I.1.9 Toute partie bornée non vide de Z admet un plus petit et un plus grand élément. Exemple L'ensemble n ? Z (n + 2)2 élément est -4. 6 est borné. Son plus grand élément est 0 et son plus petit T HÉORÈME I.1.10 Soit a et b deux entiers relatifs tels que : b 0. Il existe un entier relatif n tel que : nb a . On dit que Z est archimédien. Démonstration 1er cas : b 1 - Si a 0, il suffit de prendre n = a . - Si a < 0, il suffit de prendre n = 0. 2e cas : b On a : -b -1 1 ; donc il existe un entier relatif m , tel que : m (-b ) a. Il suffit donc de prendre : n = -m . I.1.2.d Division euclidienne dans Z T HÉORÈME I.1.11 Soit a et b deux entiers relatifs tels que b 0. Il existe un unique couple (q , r ) élément de Z×N tel que : a = bq + r et 0 r < b . Les nombres q et r s'appellent respectivement le quotient et le reste de la division euclidienne de a par b. Effectuer une division euclidienne c'est déterminer son reste et son quotient. Démonstration Existence Soit A l'ensemble de entiers naturels de la forme : a - bq (q ? Z). A n'est pas vide car a + ba est élément de A. A est une partie non vide de N, donc A admet un plus petit élément r . On a : r ?A et A? N ; donc : 0 r. Il existe un entier relatif q tel que : r = a - bq . On a : r - b = a - bq - b ; donc il existe un entier relatif q ? tel que : r - b = a - bq ? . r est le plus petit élément de A et : r - b < r ; donc : r - b ?A ; d'où : r - b < 0. Il existe donc un couple (q , r ) tel que : a = bq + r et 0 Unicité r < b . Soit (q , r ) et (q ? , r ? ) deux couples tels que : a = bq + r ; a = bq ? + r ? ; 0 On a : 0 = b (q ? - q ) + r ? - r ; donc : r ? - r = b q ? - q . Or : 0 r ? < b et -b < -r De plus : b r < b et 0 r ? < b . 0 ; donc : -b < r ? - r < b ; d'où : r ? - r < b ; c'est-à-dire : b q ? - q < b . 0 ; donc par quotient : q ? - q < 1 ; d'où : q ? - q = 0 ; c'est-à-dire : q ? = q . De plus : r ? = a - bq ? = a - bq = r ; le couple (q , r ) est donc unique. Lycée Pontus de Tyard 708-709 I.1. Les ensembles N et Z 9 M Pour démontrer qu'un objet U est l'unique objet vérifiant une propriété, il suffit de démontrer que tout objet U' vérifiant la M propriété est égal à U. Exemples 1. a = 47 et b = 9 On a : 47 = 9 × 5 + 2 et 0 2 < 9. Donc : q = 5 et r = 2. 2. a = 47 et b = -9 On a : 47 = (-9) × (-5) + 2 et 0 2 < 9. Donc : q = -5 et r = 2. 3. a = -47 et b = 9 On a : -47 = 9 × (-6) + 7 et 0 7 < 9. Donc : q = -6 et r = 7. 4. a = -53 et b = -12 On a : -53 = (-12) × 5 + 7 et 0 7 < 12. Donc : q = 5 et r = 7. Remarque Lorsque b est positif, on peut effectuer la division euclidienne de a par b , à l'aide d'une a et r = a - qb , où E désigne la fonction partie encalculatrice, en utilisant les formules : q = E b tière. Exemple Effectuer la division euclidienne de -23 564 par 1 229. -23 564 -23 564 On a : = -20 et r = -23 564 - 1 229 × (-20) = 1 016. = -19, 1 . . . ; donc : q = E 1 229 1 229 I.1.3 Numération I.1.3.a Bases de numération L'homme compte depuis l'aube de l'humanité. Il commença par compter sur ses dix doigts, aujourd'hui il utilise le système décimal, ou base dix. Ainsi le nombre que nous désignons par 51 253 est, d'après notre système usuel de numération : 5 × 104 + 1 × 103 + 2 × 102 + 5 × 101 + 3 × 100 . La base dix s'est imposée par l'usage. Les ordinateurs comptent en base deux (système binaire) ; les gens qui programment les ordinateurs en assembleur utilisent des codes en base 16 (système hexadécimal) ; les navigateurs expriment la latitude et la longitude en degrés, minutes et secondes ; ils comptent donc en base soixante (système sexagésimal). On admet le théorème suivant. T HÉORÈME I.1.12 Soit p un entier naturel supérieur ou égal à 2. Tout entier naturel x peut s'écrire de façon unique : n x= ak p k , où les ak sont des entiers naturels tels que : 0 k =0 ak < p avec an 0 si x 0 et n = 0 si x = 0. La suite a 0 , a 1 , . . . , a n est appelée développement de x en base p et l'on écrit : x = a n a n -1 . . . a 1 a 0 p . Remarque Le quotient et le reste de la division euclidienne de x par p sont respectivement : q 0 = an an-1 . . . a1 p et a0 . Le quotient et le reste de la division euclidienne de q 0 par p sont respectivement : q 1 = an an-1 . . . a2 p et a1 . On peut ainsi déterminer de proche en proche tous les chiffres de l'entier naturel x écrit en base p. Exemples 5 1. On a : 121 = 4 × 52 + 4 × 51 + 1 × 50 ; donc : 121 = 441 . 2006-2007 10 I. Arithmétique 2. Pour convertir 134 en base 7, on effectue des divisions successives par 7 en commençant par 134, comme indiqué sur la figure ci-contre. 7 On en déduit que : 134 = 251 . 134 1 7 19 5 7 2 2 I.1.3.b Système binaire Pour écrire un nombre en base 2, l'ensemble des chiffres utilisé est : {0 ; 1}. 2 Exercice I.1.1. Convertir en base dix le nombre : 10010011101 . Exercice I.1.2. Convertir en base deux le nombre : 203. 2 Solution On a : 10010011101 = 210 + 27 + 24 + 23 + 22 + 20 = 1 024 + 128 + 16 + 8 + 4 + 1 = 1 181 Solution Effectuons des divisions successives par 2 en commençant par 203, comme indiqué sur la figure ci-dessous. 203 1 2 101 1 2 50 0 2 25 1 2 12 0 2 6 0 2 3 1 2 1 1 2 0 2 On en déduit que : 203 = 11001011 . I.1.3.c Système hexadécimal Pour écrire un nombre en base 16, l'ensemble des chiffres utilisé est : {0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ; A ; B ; C ; D ; E ; F} Les chiffres A, B, C, D, E et F représentent respectivement les nombres 10 ; 11 ; 12 ; 13 ; 14 et 15. 16 Exercice I.1.3. Convertir en base dix le nombre : BAC . Exercice I.1.4. Convertir en base seize le nombre : 51 966. 16 2 1 Solution On a : BAC = 11 × 16 + 10 × 16 + 12 × 160 = 2 816 + 160 + 12 = 2 988 Solution Effectuons des divisions successives par 16 en 51 966 14 commençant par 51 966, comme indiqué sur la figure cicontre. 16 On en déduit que : 51 966 = CAFE . Lycée Pontus de Tyard 16 3 247 15 16 202 10 16 12 12 16 0 708-709 7 0 I.2. Multiples et diviseurs d'un entier relatif 11 I.1.4 Exercices I.1.a. Résoudre dans N2 le système : xy 2x . x+y = 4 ? a = -61 et b = -17 ? a = 6 327 et b = 628 I.1.f. Déterminer l'entier naturel qui divisé par I.1.b. Résoudre dans Z2 le système : 23 a pour reste 1 et qui divisé par 17 a le même xy =1 . quotient et pour reste 13. 3 x + y = -4 I.1.c. Démontrer par récurrence que pour tout I.1.g. Écrire en base 2 les nombres : 19 ; 157 et 987. entier naturel non nul n , on a : 2 I.1.h. Écrire en base 10 les nombres : 10110 ; n (n + 1)(2n + 1) 2 2 . 12 + 22 + 32 + · · · + n 2 = 11011 et 101011 . 6 I.1.i. Écrire en base 16 les nombres : 19 ; 157 et I.1.d. Démontrer par récurrence que p...