Arithmétique dans Z

Dominique Hoareau, domeh@wanadoo.fr

Table des matières

1

2

En amont.

Diviser pour mieux régner.

2.1 Division euclidienne dans N ....................

2.2 Écriture d’un entier en base b. .................. 2.2.1 Division euclidienne au service d’un codage des entiers . 2.2.2 Passage de la base 10 à une base b. . . .......... 2.2.3 Écriture en base b au service de la "potence euclidienne"

Divisibilité et congruences 3.1 Lorsque la division euclidienne tombe juste … . . . ....... 3.2 Lorsque la division euclidienne est incongrue … . . .......

Diviseurs communs

4.1 Les cavaliers de la (petite) reine . ................. 4.2 Allez Bizut montre nous tes ..., allez Bézout montre nous ton … 4.3 Une équation diophantienne incontournable . . . ........

Quelques joyaux de la reine

5.1 Décomposition en facteurs premiers . . . ............. 5.2 Petit théorème de Fermat ..................... 5.3 Théorème de Wilson ........................

Pour aller plus loin 6.1 Éléments marginaux de Z ..................... 6.2 Éléments associés . . .. ...................... 6.3 Éléments indivisibles . . ...................... 6.4 Notions de pgcd et ppem . . .................... 6.5 Anneaux intègres . ......................... 6.6 Anneaux principaux ........................ 6.6.1 Entre les anneaux euclidiens …. . ............. 6.6.2 et les anneaux factoriels, … . . .............. 6.6.3 le principal, c’est Bézout. . ................

Arithmétique dans Z

RÉFÉRENCES :

— Mathématiques d'école, Daniel Perrin, Cassini, 2005.

— Merveilleux nombres premiers, J-P. Delahaye, Belin, 2000.

— Découvrir l’arithmétique, P. Damphousse, Opuscules, Ellipses, 2000.

— Diagonales, les cahiers mathématiques du Cned, numéro 2 année 2001-2002 et numéro 2 année 2005-2006. — http ://www.irem.univ-mrs.fr/activites/superieur/arithmetique.php, R. Rolland.

— http ://perso.orange.fr/maths.rombaldi/Capes/AlgebreCapes.pdf, J-E. Rombaldi.

— http ://mon.univ-montp2.fr/claroline/document/goto/?url=%2Fpoly9.pdf&cidReq—ARI

INTRODUCTION : Il est aisé de former les entiers lorsqu ‘on utilise l’addition. On part de 1 et on ajoute à chaque fois 1 au nombre déjà construit. On a 2 = 1 +1, puis 3 = 2 + 1 = 1 + 1 + 1 et ainsi de suite. On peut dire que 1 est un générateur pour (N, +). Peut-on construire les entiers avec la multiplication ? On apprend très tôt que certains nombres entiers se cassent (ex : 6 — 2 X 3) alors que d’autres, comme 7, sont d’un seul tenant. Ces derniers, irréductibles ou insécables, s’appellent nombres premiers et, comme de véritables briques numé- riques, entrent dans la composition de tous les autres entiers. On tente d’apprivoiser ces êtres aux propriétés mystérieuses.

On propose un exposé niveau TS-Spécialité, dans l’esprit des programmes, c-à-d sous un éclairage algorith- mique. Des compléments algébriques, qui règlent, en quelques coups de cuillère à pot, certaines constructions et résolutions de problèmes, sont proposés sous la rubrique KPOUR ALLER PLUS LOIN». Dans la dernière partie du texte, on évoque, pour d’autres anneaux, la force «euclidienne» de Z (algorithme d'Eucide), sa force «prin- cipale» (Théorème de Bézout) et sa force «factorielle» (Théorème fondamental de l’arithmétique).

On suppose connus l’ensemble N des entiers naturels et l’objet Z des relatifs munis de l’addition, de la multi- plication et de la relation d’ordre total notée < . On dispose d’une batterie de bons sous-objets de Z (comme, par exemple, l’ensemble des entiers pairs) : ce sont les

nZ = {nq, ge Z} dont les éléments, appelés multiples de n, forment une suite arithmétique de raison n. Question du jury : Qui se cache derrière 2Z.3Z = {xy € Z, x e 2Z et y € 3Z}? Réponse : «lls se multiplièrent et eurent beaucoup d'enfants.»

POUR ALLER PLUS LOIN : L'ensemble Z est un anneau commutatif, unitaire, intègre, et totalement ordonné. Les nZ, dont n constitue un générateur, vérifient

1. la stabilité pour la loi additive : V(k,1) € nZ, k+1€ nZ. 2. la stabilité pour le passage à l'opposé : Vk € nZ, —kE nZ. 3. la propriété d'absorption : Vk € nZ, VIE Z, klEe nZ.

donc sont "des! idéaux (monogènes ou principaux) de Z.

Exercice 1 : Si a,b € Z vérifient a + b € nZ et ab € nZ, alors a? € nZ. Corrigé : Il suffit de relier a +b, ab et a? : a est racine du trinôme x? — (a+b)x + ab, e-à-d a? = (a+ ba — ab. Question du jury :

1. Pour n,m € N, donner une condition nécessaire et suffisante pour avoir nZ = mZ.

2. Sur les traces de Galilée, peut-on mettre en bijection Z et sa partie stricte N?

Réponse : Il suffit d'envoyer n sur 2n si n € N, sur —2n — 1 sin € Z- \ {0}.

Arithmétique dans Z

1 En amont.

On rappelle une propriété fondamentale de N, qui kirrigue» la suite du texte :

Bon ordre sur N : 1. Toute partie non vide de N admet un plus petit élément (pour l’ordre usuel).

2. Toute partie non vide et majorée de N admet un plus grand élément.

Voici deux autres incarnations du bon ordre sur N : 1. le théorème de récurrence,

2. la descente infinie de Fermat.

Propriété :

Il n°y à pas de suite strictement décroissante à valeurs dans N.

Preuve : On raisonne par l'absurde. Si tel est le cas, soit (u,) un tel objet. L'ensemble de ses valeurs est une partie non vide et minorée (par 0) de N donc admet un minimum, un certain un. Puisque (u,) décroît strictement, un+1 < un, ce qui contredit le statut de un.

2 Diviser pour mieux régner. 2.1 Division euclidienne dans N

Théorème :

Soit a, b deux entiers naturels avec b > 0. Alors il existe un unique couple (q,r) € N° tels que a=bq+r et O<7r <b.

On dit que a est le dividende, b le diviseur, q le quotient et r le reste dans la division de a par b.

Preuve : Le lecteur peut rédiger la preuve de l’existence de (q,r) à partir de l’algorithme des différences :

Algorithme :

— Données : a, b dans N avec a > b.

— Variables : get r.

— Initialisation : q = 0 et r = a. On a la relation a = bq +7r à l’entrée de boucle.

— Début boucle : Tant que r > b, faire

— Corps de la procédure : q3=q+1,r=7r—b. Si on commence un tour de boucle avec a = bq+r, à la fin de boucle, on a encore a = bq+7r : r a diminué de b et simultanément, q augmentant d'une unité, bq augmente de b.

— Fin de boucle : Renvoyer q et r.

La boucle "While" se termine parce que la partie Q = {k€ N, a — bk > 0} de N, qui est non vide (0 € Q), possède un plus petit élément.

Pour l’unicité, on envisage deux couples (q,r) et (g',r”) qui conviennent : b(q—q') = r'—7r avec 0 < r,r' <b—1. SigaÆ£#g,lqa—-g |>1doncb|qg-gqg|>b,|r—-r1|> b. Contradiction puisque la distance entre r et r” (compris tous les deux entre 0 et b — 1) est inférieure à b — 1. Ainsi, g = q’, puisr = a—bq—=a—bq = 7.

Arithmétique dans Z

Exemple : On effectue la division euclidienne de 347 par 5. Au lieu de, comme le ferait une machine, retrancher (à 347) 5 une première fois, 5 une deuxième fois, ... jusqu ‘à obtention d° un reste plus petit que 5, on utilise les bonnes

vieilles tables de multiplication : 347 = 60 x 5 + 47, puis 347 = 60 x 5 +9 x 5 +2 = 69 x 5 +2.

On a évité 69 soustractions successives.

Exercice 2 : — Anne, ma soeur Anne, ne vois-tu rien venir ? — Je ne vois rien que le soleil qui poudroie, et l'herbe qui verdoie.

Après avoir listé les premiers éléments positifs de 2Z et 3Z, déterminer 2Z N 3Z. Pourquoi 2Z U 3Z n‘’est-il pas un "bon" sous-objet de Z? Déterminer 2Z + 3Z.

Corrigé : On vérifie que 6Z € 2Z N 3Z. Soit à présent n € 2Z N 3Z. On envisage la division euclidienne de n par 6 : n = 6q +7 avec 0 < r < 5. Puisque r = n — 6q avec n € 2Z et —6q € 2Z, r € 2Z. De même r € 3Z. Le seul entier entre 0 et 5 multiple de 2 et 3 est 0, donc n = 6q € 6Z.

On a 2 € 2Z donc 2 € 2Z U 3Z. De même, 3 € 2Z U 3Z. Or 2+3 = 5 n‘appartient pas à 2Z U 3Z. Pour pallier ce défaut de stabilité, on envisage 2Z + 3Z. On peut vérifier que 2Z + 3Z a toutes les bonnes propriétés de 2Z, contient 2Z U 3Z et est le plus petit sous-objet "efficace" de Z contenant 2Z U 3Z. Puisque 2x (—1)+3x1 = 1, onale2Z+3Zet, pour toutneZ,n=nx1=2x(-n)+3xn € 2Z +37. Puisque l'inclusion 2Z+3Z C Z est automatique, on à 2Z + 3Z = Z.

Exercice 3 : (Un sacré concurrent) Un candidat au CAPES a 461 exercices à caser dans ses leçons d’oral. Un tantinet rigide, il suit deux règles : 1. Il ne commence pas une leçon avant d’avoir fini la précédente. 2. Chaque leçon doit contenir le même nombre d ‘exercices. Avant les oraux, le candidat a préparé 14 leçons. Combien d ‘exercices contiennent les leçons achevées ? Combien d ‘exercices pour la dernière leçon ?

Corrigé : Puisque 461 & 147, seules 13 leçons sont complètes. On a 461 — 13 x 35 + 6 donc une première réponse est : 13 leçons complètes à 35 exercices et 1 leçon à 6 exercices. Y-a-t-il d’autres combinaisons ? On peut essayer de réduire le nombre d'exercices sur les leçons complètes et avoir une incomplète plus étoffée. On a 461 — 13 x 34 + 19, ce qui donne un autre couple solution (34; 19). On a 461 — 13 x 33 + 32, qui donne une autre solution (33;32). La tentative "leçon complète à 32 exercices" est infructueuse : puisque 461 = 13 x 32 + 45 = 14 x 32 + 13, il s’agirait de 15 leçons préparées.

Corollaire : «Z est euclidien.» Soit (a,b) € Z x Z*. Alors il existe un couple (q,r) € Z? tel que

a = bg + r avec la mesure du reste : r =0ou|r|<|b|.

Remarque : On perd dans Z l’unicité du quotient et du reste comme le prouvent les égalités

24=5x4+4et24=5x5—1.

POUR ALLER PLUS LOIN :

Application : (Sous-groupes additifs de Z et idéaux de l’anneau Z)

Arithmétique dans Z

1. Les sous-groupes de (Z, +) sont exactement les nZ = {ng, q € Z}, pour n € N.

2. Les idéaux de (Z, +, x) sont exactement les nZ. On dit que Z, qui ne possède que des idéaux monogènes, est un anneau principal. Les cas n = 0 et n = 1 donnent lieu à {0} et Z.

Preuve : Les nZ sont des sous-groupes de Z. Réciproquement, soit A un sous-groupe de Z, H % {0}. La partie H A N* non vide de N a un plus petit élément qu’on appelle n. Clairement, nZ € H. À présent, si x € H, par division euclidienne, x s'écrit æ = nq + r, avec 0 < r < n. Ainsi r = x — nq est dans H et dans N*, et r — 0 par statut de n. Finalement x = nq € nZ. On retiendra qu'un générateur d'un sous-groupe H ZÆ {0} de Z est le plus petit entier naturel non nul qui se trouve dans A.

Un idéal 7 de Z est déjà un sous-groupe de Z, donc de la forme nZ, avec n € N. Puisque, réciproquement, chaque nZ est un idéal, les idéaux de Z sont exactement les nZ.

2.2 Écriture d ‘un entier en base b.

2.2.1 Division euclidienne au service d’un codage des entiers

Théorème : Soit b E N, b > 2. Tout entier a > 0 s’écrit de façon unique :

(CH) a = anb" +... + ab? +aib+ao oùneN,&EeN,0<a;<bet a, #0.

Dans cette écriture dite en base b, les a; sont appelés chiffres de a en base b. On note a = &n---&1@o.

Preuve : Pour l’existence de l'écriture (*K), montrer, par récurrence sur N € N, la propriété : E(N) Tout entier a compris entre 1 et N a une écriture (K).

L'initialisation est facile pour 0 < N < b. Si E(N) est vraie avec N > b — 1, montrer E(N + 1) en envisageant la division euclidienne de N +1 par b.

Pour l’unicité, montrer, par récurrence, la propriété U(N) : Si un entier a compris entre 1 et N a deux écriture

a = an" ++: + a2b° + a1b + ao = 4,0" +: + a,b° + ab + a,

+ — à =, alors m = n et, pour tout 1 <i <n, a; = af.

Question du jury : Que penser de l'affirmation : «le théorème de la division eulidienne est, tacitement, le résultat mathématique le plus universellement utilisé» ?

Exemple : (d’après D. Perrin, Mathématiques d'école, Cassini, 2005)

Dans la Gaule antique, en Septimanie (où on avait la manie de compter en base 7), le druide Pacorabanix, fort versé en numérologie, avaient prévu la fin du monde pour l’an 5555. Vérifier que ce nombre, remarquable en base 7, l’est encore en base 10. On l’a échappé belle!

2.2.2 Passage de la base 10 à une base b.

Algorithme : — Données : a, b dans N avec a > b < 2. — Variables : ne Net rsit E N.

Arithmétique dans Z

— Initialisation : n = 0 et rsit = 0. — Début boucle : Tant que a > 0, faire — Corps de la procédure : — q = quotient de a par b — r =reste de a par b — rslte rslt+r x b” -n—n+l _—

— Fin de boucle : Renvoyer rsit.

Question du jury : : Qu'est-ce qui garantit la fin de boucle ?

Réponse : Descente infinie de Fermat : Dans N, on ne peut pas diviser sans fin sauf par 1, sans être confronté à une contradiction.

Exercice 4 : (La bonne année!) Donner l'écriture de 2008 en base 7.

2.2.3 Écriture en base b au service de la "potence euclidienne"

On pourra illustrer par la bonne vieille potence l'algorithme suivi par un élève du primaire pour effectuer la division de 347 par 5 : — Dans 34, combien de fois 5? Il y va 6 fois. 6 x 5 — 30, qu ‘on enlève de 34. Il reste 4. On abaisse le chiffre 7 des unités. — Dans 47, combien de fois 5? Il y va 9 fois. 9 x 5 = 45, qu'on retranche à 47. Il reste 2, plus petit que 5. — Conclusion : Le quotient est 69 et le reste et 2. On justifie l'algorithme. Soit à, b € N, b > 0, get r les quotient et reste de la division de a par b. On envisage l’entier a = 10a+aoù0<a<9. 1. Quel est le lien entre l'écriture décimale de a et celle de a/ ? 2. On veut effectuer la division euclidienne de a’ par b. (a) Vérifier que a’ = b(10q) + 10r + a. (b) On appelle g' et r’ les quotient et reste de la division de 10r + & par b. Vérifier que 0 < q! < 9.

(c) En déduire le quotient et le reste de la division de a’ par b.

3 Divisibilité et congruences 3.1 Lorsque la division euclidienne tombe juste …

Définition :

Pour a et b dans Z, on dit que

— b divise a

— ou b est un diviseur de a

— ou encore à est un multiple de b,

et on note b | a, lorsque a € DZ, c-à-d lorsqu'il existe g € Z tel que a = bq.

Si, pour x € Z, D, désigne l’ensemble des diviseurs de x, on a la correspondance :

bas aZ CbZESD, € Da.

Remarque : Lien avec l’ordre usuel sur N* : Va,b E N*, bla = b< a.

Arithmétique dans Z

Exemple : si on écrit une séquence de 3 chiffres et si on répète le motif pour obtenir un entier N de 6 chiffres (en base 10), on est certain d’avoir un multiple de 7. En effet, on peut poser N = abcabc et on a

N = abc x 1000 + abc = 1001 x abc = 7 x 11 x 13 x abc.

Exercice 5 : Qui ne saute pas n’est pas de Montpellier !

Pour la finale de la coupe de France de football, les dirigeants du Montpellier Hérault proposent de louer des cars afin d'emmener des supporters à Paris. On sait qu'il y aura entre 2000 et 3000 supporters qui feront le déplacement. Pour des raisons pratiques, les dirigeants souhaitent que chaque car contienne le même nombre de passagers. Dans un premier temps, la répartition envisagée correspond à 45 personnes par car mais il reste 6 personnes sans place. On réalise qu'avec un car de moins, tout le monde à une place dans les conditions requises. Déterminer le nombre N de supporters qui feront le déplacement.

Corrigé : Soit s le nombre de supporters par car et n le nombre de cars retenus. On a N = 45(n +1) +6 = 45n +51

et, puisque 2000 < N < 3000, il vient 44 < n < 65. Par ailleurs, N = ns donc 45n + 51 = ns, 51 — n(s — 45), n | 51. Ainsi, n € {1,3,17,51} puis n = 51 et N = 2346. Exercice 6 : Trouver les entiers n € N* tels que

1. nÎn+s.

2.n—-1l|n+11.

3. n —4|3n +24. Corrigé : Pour 1, si n convient, n est un diviseur de 8 et réciproquement, 1, 2, 4 et 8 conviennent. Pour 2,

sin—1|n+11, N = n—1 divise 12 et on étudie la réciproque. Pour 3, si n — 4|3n +24, N = n — 4 est un diviseur de 36 et réciproquement, …

Exercice 7 : Quels sont les entiers naturels non nuls n qui vérifient n + 1 | (n? +1).

Corrigé : Sin convient, avec n?+1=(n+1}n-n+1=(n+1}n-{(n—1),onan+1|(n—1). Ceci impose n—1=0,n= 1. Réciproquement, n = 1 convient.

Exercice 8 : Quels sont les entiers relatifs n qui vérifient n — 3 | (n° — 3)?

On pourra vérifier l'existence de q € Z tel que n° — 3 = q(n — 3) + 24.

Tout entier naturel supérieur à 2 possède au moins deux diviseurs positifs distincts : 1 et lui-même. Qui sont les entiers minimalistes pour cette règle ?

Définition :

Un entier naturel p est dit nombre premier si p £ 1 et si p n’a que deux diviseurs positifs : 1 et lui-même. Les nombres 2, 3, 5, 7, 11, 13, 17 sont des nombres premiers.

Exemple : Pour n > 2, une somme $ de n entiers impairs consécutifs n’est jamais premier. En effet, on peut écrire

S=(2k+1)+(2k+1+2)+(2k+1+2X2)+...+(2k+1+2x(n—1)),, kEZ

donc

S=nx(2k+1)+2xX(1+...+(n—1)) =n(2k +1) +n(n—1) =n(2k+n), ce qui garantit que n (distinct de 1 et de S) divise S. Question du jury : Vrai ou faux : Pour tout entier naturel n, n? + n + 41 est un nombre premier. Réponse : Avec n = 41, on a 41? + 41 + 41 = 41 x (41 + 1 +1) = 41 x 48.

Exercice 9 : (Un seul mot d'ordre : factoriser)

Arithmétique dans Z

1. Pour tout entier n > 3, n°? + 2n — 3 n°est pas premier.

2. Même conclusion pour n° + 4 dès que n > 1. Commentaire : "I worked on this problem for days, applying in vain all the number theory I knew or could learn. Finally, sufficiently humbled now, I asked the buddy (who had given me the problem) how to solve this problem. He said "Dummy, the polynomial factors !". And indeed it does. It is the difference of two squares in disguise : … My "irrational exuberance"" was quelled and I learned my first painful lesson in humility."

3. Même conclusion pour n° +n*+1sin > 1.

4. Pour n,m € N*,sin > 1oum > 1, alors n4+ 4m n’est pas premier.

Exercice 10 : (D'après baccalauréat Dijon session 1973) 1. Le nombre 214 — 1 est-il premier ?

2. pet q étant deux entiers naturels non nuls, quel est le reste de la division par 2? — 1 du nombre 2P4 — 2747? En déduire que, si 2° — 1 est premier, alors n est premier.

Commentaire : Les nombres M, = 2" — 1, considérés par Mersenne en 1644 pour la recherche de grands nombres premiers, portent son nom. En 1999, le plus grand nombre premier connu est M6o72593.

Exercice 11 : «Tout premier positif de Z est un nombre premier.» Soit p € N. On envisage les énoncés : 1 p#0,p£letVabeN plab=plaoup]b. 2. pest un nombre premier. Montrer que 1. implique 2. Corrigé : Sous 1., p £ 1. Soit a un diviseur de p dans N. On écrit p — ab et, d’après 1., on peut supposer que

a = pa, à € N. Il vient p = pab, p(1 — ab) = 0 avec p £ 0 et, puisque Z est intègre, ab = 1, a | 1, a = 1, donc a = p et p est premier.

Exercice 12 : (Une grande plage de nombres composés) Soit n € N. En utilisant la quantité (n + 1)!, construire n nombres entiers consécutifs non premiers.

Commentaire : Il existe des intervalles arbitrairement longs sans nombre premier. Pourtant, il existe une infinité de nombres premiers (cf infra). On pense même qu’il existe une infinité de nombres premiers p dont le successeur impair p + 2 est aussi premier.

Propriété : (Fondamentale)

Tout entier n distinct de 1 admet un diviseur premier p.

Preuve : On suppose n > 1. Si D, désigne l’ensemble des diviseurs de n, D, \ {1}, qui contient n, possède un plus petit élément p. Si q | p, alors q | n et, par conséquent, q = 1 ou q — p, donc p est un diviseur premier de n.

Application : (Partie existencielle du théorème fondamental de l’arithmétique) Tout entier n > 2 peut s’écrire comme un produit de facteurs premiers.

Preuve : Par récurrence, laissée au lecteur.

Application : (Théorème d’Euclide ou le parangon de la preuve mathématique) Il existe une infinité de nombres premiers.

Arithmétique dans Z

Preuve : On raisonne par l'absurde en envisageant la liste (finie) {p1,--: ,p,} des nombres premiers. On pose : M=p x... X pn +1.

Soit p un diviseur premier de M. On a p > p, sous peine de voir p | (M — p1 X --- x p,), i.e p | 1. Enfin, p > Pa est exclu puisque p, est supposé être le plus grand nombre premier.

Commentaire : Si on note, pour x € R, (x) le nombre des nombres premiers au plus égaux à +, la fonction xt (x), clairement croissante, tend vers +oo avec x. En 1896, Hadamard et La Vallée-Poussin démontrent une estimation en +o conjecturée par Gauss et Legendre :

Application : («Sonwil») Soit p € N tel que (p — 1)! = —1(p). Alors p est premier.

POUR ALLER PLUS LOIN : La divisibilité restreinte à N, qui vérifie Va,b,ceN, a)}a (réfléxivité), b|aet a|b— a = b (antisymétrie), c|bet b|a = c|a (transitivité),

est une relation d ‘ordre partiel sur N.

1. Lien avec l’ordre usuel sur N* : Va,bE N*, bla = b< a.

2. O est le plus grand élément et 1 le plus petit dans (N, |).

3. N\{0;1} n’a pas de plus petit élément. Sinon, si m convient, m | 2 et m | 3 donne m | 1, m = 1, ce qui est exclu.

4 N\{0;1} n’a pas de plus grand élément. Sinon, si M convient, 2M & {0;1} et 2M | M, ce qui conduit à 2Mq = M avec q € N. Aussi, puisque M = 0 est exclu, 2q = 1. Impossible dans N.

5. L'application n + nZ est bijective et strictement décroissante de (N, |) sur l’ensemble Z des idéaux de Z muni de l’inclusion.

6. Un nombre premier est un élément minimal parmi les entiers naturels distincts de 1, et p est premier si, et seulement si, pZ est maximal dans l’ensemble TZ \ {Z}.

3.2 Lorsque la division euclidienne est incongrue …

Dès l’école primaire, on peut déterminer l'heure du réveil si on sait que le coucher a lieu à 22 heures et que la nuit de sommeil est de 8 heures. Au lycée, on laisse de côté les aiguilles de pendule et on enroule sur un cercle une ficelle pour mesurer les angles orientés. On peut alors affirmer qu’un angle de 3 radians a pour mesure principale —T. En route vers les modules.

Définition : Soit n € N*. On dit que a, b € Z sont congrus modulo n et on écrit (notation introduite par Gauss, en 1801)

a=b(modn) ou a=bi(n),

si n divise la différence a — b, ou encore a — b € nZ. En particulier, b| a & a = 0 (b).

Arithmétique dans Z

Exemple : Les entiers pairs sont les éléments de 2Z qui sont congrus à 0 modulo 2. Un nombre écrit dans le système décimal est congru, modulo 10, à son chiffre des unités.

Exercice 13 : (Roméo doute-t-il de l’amour de Juliette ?) Roméo à une marguerite à 2183 pétales. I les effeuille un à un en disant toujours dans le même ordre : «un peu», « beaucoup», «passionnément», «à la folie», «pas du tout». Quid de l’amour de Juliette ?

Exercice 14 : (Happy birthday) Sachant que Roméo à épousé Juliette le premier janvier de l’année bissextile 2000 (qui était un samedi) déterminer le jour de la semaine pour leur 100"® anniversaire de mariage.

Corrigé : Entre le 01 — 01 — 2000 et le 01 — 01 — 2100, les années bissextiles sont les 2000 + 4k où 0 < k < 24 donc le nombre de jours N qui sépare les deux dates est N = 100 x 365 + 25. On écrit

ul

N=(7TxIA4+2)x(7x52+1)+7x3+4=6(7).

Puisque les multiples de 7 ne modifient pas le nom du jour, le 01 — 01 — 2100 sera un vendredi.

POUR ALLER PLUS LOIN : La congruence modulo n > 0, qui vérifie

Va,b,ceZ, a=a(réfléxivité), a=b=b=a (symétrie), a=betb=c—a=c (transitivité),

est une relation d'équivalence sur Z. L'ensemble quotient est noté Z/nZ, ses éléments k,k € Z.

Si k € Z, grâce à la division euclidienne (existence) de k par n, k est congru à l’un des nombres 0, …, n — 1. Réciproquement si k = r (n) avec 0 <r <n—1, on à k = nq+r et, par unicité du quotient et du reste dans la division euclidienne, r est le reste de k par n. Ainsi, tout nombre k est congru à l’un des nombres 0, …, n —1

et un seul. On peut écrire :

Z/nZ = {0,1,.,n—1} avec card(Z/nZ) = n.

Théorème : Congruences et opérations dans Z

Soit n € N°, a, a/,b,b! € Z tels que a = a’ (n) et b = b'(n). Alors, modulo n, 1 a+b=a+b. 2. ab = a'b'.

POUR ALLER PLUS LOIN : Les lois de composition interne

(DE EkT+I et (kDEkxI

sont ainsi correctement définies, et donnent à Z/nZ une structure d’anneau commutatif.

Exemple : Pour tout n € N, N = 321 4942 est divisible par 7. En effet, N — 3 x 9% +22 x 2° et, modulo 7, N=3x2"+4x 27-99 x (3+4)=0.

Question du jury : 1. Retrouver (et démontrer) les critères usuels de divisibilité (par 2, 5, 3, 9 et 11) pour un entier écrit en base 10.

2. Les nombres suivants sont-ils premiers : 10%7 + 1, 10%7 — 1? On pourra les regarder modulo 11 et 9.

10

Arithmétique dans Z

Exercice 15 : Roméo a écrit son numéro de téléphone sur un papier pour Juliette. Mais il a plu sur le papier et un chiffre est illisible : 02 98 e 3 81 98. Juliette se souvient que Roméo lui a dit : «mon numéro de téléphone est divisible par mon nombre fétiche, le 11». Comment fait Juliette pour retrouver le chiffre manquant ?

Exercice 16 : On sait que l’entier 1221 (écriture en base 10) est divisible par 11 puisque la somme alternée de ses chiffres vaut 1 — 2 +2 —1 —0(. Montrer, plus généralement, qu ‘en base b > 2, le nombre N = 122::-21 à k > 3 chiffres n ‘est pas premier.

Corrigé : On écrit

N=1+960+90 +... +R ET LE BEBE HR D ++. + = 1+b+... +66 2101 +0)

donc, avec 1+b>1et1+b+...+b*-25>1, N n'est pas premier. Exercice 17 : 1. Soit p > 3 premier. Alors p? + 2 est composé. 2. Si p = a? + b? est un entier impair somme de deux carrés, alors p — 1 est un multiple de 4. Corrigé : On a p = 1(3) ou p = 2(3) done p? = 1(3), p? +2 = 0 (3). Ainsi, 3 | (p? +2) et p? +2 n’est pas

premier. Pour la deuxième question, on remarque qu’un carré est 0 ou 1 modulo 4, donc une somme de deux carrés est 0, 1 ou 2. Avec p impair, p = a? + b? est 1 modulo 4, d’où le résultat.

Exercice 18 : Dans le groupe additif Z/7Z, la classe 1 est un générateur puisque, par additions répétées de 1, on construit tous les éléments de Z/7Z. Quels sont les autres générateurs de Z/7Z ? Exercice 19 : (D'après baccalauréat Session 1970 Aïx-en Provence)

1. Si aucun des trois entiers a, b et c n’est divisible par 3, alors a? + b? + c? est un multiple de 3.

2. En remarquant que 999 = 27 X 37, montrer que pour tout entier positif n 10° = 1 (37) puis trouver le reste de la division de 1010 + 1020 + 10% par 37.

Exercice 20 : (Un tour de magie) On considère le nombre premier p = 5. Élever au carré, ajouter 11, diviser par 24. Quel est le reste dans la division ? Idem avec p = 31. Idem avec un nombre premier de votre choix. Est-ce un hasard ?

Exercice 21 : (Vers le petit théorème de Fermat)

5

1. Pour a € Z, factoriser a° — a en faisant apparaître 3 facteurs de degré 1 et 1 facteur de degré 2.

2. En déduire la congruence a° = a (5).

Exercice 22 : (Chiffre des unités de 20042%, adapté d ‘un exercice d ‘oral de Centrale) 1. Conjecturer les restes des puissances de 4 modulo 10.

2. Montrer, pour tout n € N*, Pin): 4%2=6(10) et 47*#1=4(10). 3. Conclure.

Exercice 23 : (Primalité de n* + 4”, adapté d’un exercice d ‘oral de Polytechnique) Soit un entier n > 5.

1. Le nombre n* + 4" est-il premier si on suppose que n est pair ?

11

Arithmétique dans Z

2. On suppose que n n’est pas congru à 0 modulo 2 et modulo 5. Montrer que n4 +4" = 0 (5) puis conclure.

Exercice 24 : (Le scratch du F5 par Euler) 1. Justifier les congruences 5 x 27 = —1 (641) et —54 = 24 (641). 2. Montrer que F5 = 22 +1 = 232 + ] n’est pas premier.

Commentaire : On admet que F, F2, F3 et FA sont premiers. En 1640, Fermat écrit à Mersenne que tous les nombres F,, qui portent maintenant son nom, sont premiers. Euler contredit Fermat en 1732. À ce jour, on sait que F, est composé pour 5 < n < 30 et la conjecture sur les F} s’est même retournée : on pense maintenant qu'aucun F, n’est premier à partir de F3. Exercice 25 : — Déterminer tous les entiers premiers p tels que p+ 10 et p + 14 soient aussi premiers. On pourra envisager toutes les congruences possibles de p modulo 3. — Déterminer tous les entiers premiers p tels que 4p?+1 et 6p? +1 soient aussi premiers. On pourra envisager toutes les congruences possibles de p modulo 5. — Déterminer tous les entiers premiers p tels que p +2, p+6, p+8, p +12 et p + 14 soient aussi premiers. On pourra envisager toutes les congruences possibles de p modulo 5.

A Diviseurs communs

4.1 Les cavaliers de la (petite) reine

— Anne, ma soeur Anne, ne vois-tu rien venir ? — Je vois deux cavaliers qui viennent de ce côté mais ils sont encore loin. POUR ALLER PLUS LOIN : Voici une présentation rapide des notions de pgcd et ppcm. Pour a et b entiers relatifs, via la division euclidienne, les idéaux aZ + bZ et aZNbZ s’écrivent (de façon unique) dZ et mZ (d,m € N). On vérifie que : 1. dZ, = aZ, + DZ, est le plus petit idéal de Z qui contient aZ et bZ. 2. mZ = aZ N bZ est le plus gros idéal de Z contenu dans aZ et bZ. Par dualité, 1. l’entier d est le plus grand élément au sens de | parmi les diviseurs communs de a et b : il est appelé Plus Grand Commun Diviseur de a et b (notation : d = a A b ou d = pgcd(a, b)). 2. l’entier m est le plus petit élément (pour |) parmi les multiples de a et b : il est appelé Plus Petit Commun Multiple de a et b (m = a V b ou m = ppem(a, b)). Lorsque d = 1, on dit que a et b sont premiers entre eux et sur un plateau :

du,v € Z, au + bu = 1 (Relation de Bézout).

Voici une présentation plus pédestre qui repose aussi sur la division euclidienne.

Définition :

Soit a,b € N non tous deux nuls.

1. L'ensemble D, des diviseurs positifs communs de a et b est une partie de (N, <) non vide (1€ D, 4) et majorée par min (a, b) donc D, admet un plus grand élément pour <. On l’appelle le plus grand commun diviseur de a et b et on le note pgcd(a, b).

2. L'ensemble M, 4 des multiples > 0 communs de a et b est une partie de (N, <) non vide (ab € M, x) et minorée par max (a,b) donc M, admet un plus petit élément pour < . On l'appelle le plus petit commun multiple de a et b et on le note ppem(a, b).

3. Lorsque le pgcd de a et b vaut 1, on dit que a et b sont premiers entre eux et on note a Ab = 1.

12

Arithmétique dans Z

Question du jury : 1. Pourquoi ne peut-on pas définir pgcd(0, 0) ? Pour a,b > 0, que valent pgcd(a, 0), pygcd(a, 1) et pgcd(a, b) lorsque b | a?

2. Primalité vs primalité relative : Peut-on avoir a et b premiers entre eux avec a et b non premiers ?

Exercice 26 : (Une batterie d’entiers premiers entre eux) Pour p premier et a € Z, a À p = 1 si, et seulement si, p ne divise pas a.

Corrigé : Si a et p sont premiers entre eux, on ne peut avoir p | a sous peine de voir pgcd(a,p) > p > 1. Réciproquement, on suppose que p ne divise pas a. Soit n un diviseur commun de a et p. Puisque n | p et p premier, n vaut 1 ou p. Puisque p ne divise pas a, nécessairement n = 1, ce qui montre que D, , = {1} et pgcd(a,p) = 1. Question du jury : :

1. Qu'est-ce que le crible d’Eratosthène ?

2. On choisit 100 nombres premiers entre eux deux à deux compris strictement entre 1 et 1992. Pourquoi y-a-t-il nécessairement dans cette liste un nombre premier ?

Réponse :

1. On veut les entiers premiers inférieurs à un certain n. On écrit tous les entiers de 2 à n. On marque tous les multiples de 2 sauf 2, puis on répète la manipulation avec le premier nombre plus grand que 2 encore présent, et ainsi de suite. Il est inutile de poursuivre le marquage à partir du premier nombre non marqué k > /n. En effet, son premier multiple non marqué est & x k > n.

2. Si les 100 nombres choisis sont composés, chacun a au moins un diviseur premier strictement inférieur à 199. Par le crible d'Eratosthène, après avoir éliminé les multiples de 2 (autres que 2) au nombre de 98 et les multiples de 3, il y a moins de 100 nombres premiers strictement inférieur à 199, donc au moins deux des 100 nombres choisis ont un diviseur premier en commun. Contradiction !

Propriété : (Caractérisation du pgcd)

Soit a,b € N non tous deux nuls, d € N. On envisage les trois énoncés :

i) d|a, d|bet, pour tout diviseur ô commun de a et b, 6 | d.

ii) L'entier d est le pgcd de a et b, ï.e le plus grand élément de D, x pour <. ii) On peut écrire a = da’, b = db’ avec a’, d'EN et a Ab’ —1.

POUR ALLER PLUS LOIN : La proposition ti) peut se traduire par « d'est, pour |, le plus grand élément de D, 4» ou encore

«d est un minorant de {a,b} pour l’ordre | et d est supérieur à tout minorant de {a,b}»

« d'est, pour |, la borne supérieure de la partie {a,b} de N.»

Sans... : Onaïi) = ii) — titi).

Avec Bézout (cf infra) : On a ii) = à).

Preuve : instructive, laissée au lecteur.

13

Arithmétique dans Z

4.2 Allez Bizut montre nous tes …, allez Bézout montre nous ton …

Soit a,b € N non tous deux nuls et à € N. Puisque 6Z est stable par "combinaison d’anneau", l’entier 0 est un diviseur commun de a et b si, et seulement si, Ô est un diviseur commun de a — b et b.

Exercice 27 : En divisant 6732 et 564 par un même nombre b, on trouve des restes de 24 et 18. Quel peut être b?

Corrigé : Avec les données, on vérifie que b est un diviseur commun de 6732 — 24 — 6708 et 564 — 18 — 546, donc est un diviseur de d — pgcd(6708, 546). Le lecteur courageux montre, par l'algorithme des différences, que d — 78. Ainsi, b | 78 avec la contrainte b > 24, ce qui donne b — 26, ou 39 ou 78.

Propriété : (Vers l’algorithme d’Euclide) Soit a, b € N, b 0. On effectue la division euclidienne de a par b :

a=bq+r, qgreN, 0<r<b. Les diviseurs communs de a et b sont exactement les diviseurs communs de b et r = a — bq : Dub — Do,r.

Aussi, le pgcd de a et b est le pgcd de b et r.

Algorithme : — Données : a, b dans N. — Variables : r,s,teN — Initialisation : r = max (a,b), s = min (a,b) et t — 0. — Début boucle : Tant que s > 0, faire — Corps de la procédure : — t= reste de r par 5 —T—=Ss — ST — Fin de boucle : Renvoyer r.

La procédure renvoie le dernier reste non nul. C’est r! Ce n’est pas s car, à la fin, s — 0. Question du jury : : Qu'est-ce qui garantit la fin de boucle ?

Réponse : Descente infinie de Fermat : Dans N, on ne peut pas construire une suite strictement décroissante d'’entiers naturels (suite des restes). sans être confronté à une contradiction.

Exemple : On applique l’algorithme d’Euclide pour avoir pgcd(584, 142). On a 584 — 142 x 4 + 16 donc pgcd(584, 142) — pgcd(142, 16). Nouvelle boucle : 142 = 16 x 8 + 14 donc

pgcd(584, 142) = pgcd(142, 16) = pgcd(16, 14). Encore un tour : 16 — 14 x 1 +2 donc pgcd(584, 142) — pgcd(142, 16) — pgcd(16, 14) — pgcd(14, 2).

Enfin, 14 — 2 x 7 +0. Le dernier reste non nul de l’algorithme est pgcd(584, 142) — 2.

14

Arithmétique dans Z

Théorème : (Théorème de Bézout)

Soit a, b € N, non tous deux nuls et d € N. Les propositions suivantes sont équivalentes : 1. dest le pgcd de a et b 2. d|a,d|bet il existe u,v € Z tels que d = au + bu.

En particulier, a et b sont premiers entre eux (pgcd(a,b) = 1) si, et seulement si, a et b sont «Bézout entre eux» : il existe u,u € Z, au + bu = 1.

Question du jury : 1. Y-a-t-il unicité du couple (u, v) ?

2. Vrai ou faux : Deux entiers naturels consécutifs sont premiers entre eux.

Réponse : 1. au + bu = a(u + kb) + b(v — ka), pour tout k € Z. 2. PourneN,net n +1 sont «Bézout entre eux» puisque (—1)n + 1(n + 1) = 1, donc sont premiers entre eux.

Preuve : On montre que 2 — 1. Si il existe u,v € Z tels que d = au + bv, tout diviseur commun de a et b divise aussi d et, comme d est par ailleurs un diviseur commun de a et b, d est bien le pgcd(a, b). Pour l’autre implication, on suivra

Algorithme : (d”Euclide étendu) — Données : a,b > 0 non tous deux nuls.

— Initialisation : — To—=a — T1 —= b — U0 — 1 — OU] — 0 — V0 — 0 — OU] — 1

On a les relations ro = uoa + Vob et r1 = uia + v1b à l'entrée de boucle. — Tant que R1 > 0, faire

— q = quotient de ro par ri

— r = reste de ro par 71

— U = Uo — QU1 Et U = Vo — QU

= F0 T1 = N=T — Uo — ui — OU = U — Vo — V1 — VU =

Si, à l'entrée de boucle, on a ro = uoa + Vob et r1 = ua + v1b, on les a aussi à la sortie de boucle. — Fin de boucle.

Propriété : (Applications fondamentales de l'identité de Bézout)

15

Arithmétique dans Z

1. clabetcAa=1= c|b (Lemme de Gauss) 2. Si p est premier, alors p | ab = p | a ou p | b. (Lemme d‘euclide, pZ idéal premier de Z) POUR ALLER PLUS LOIN : Sous la condition «p premier», l'idéal pZ, s "il contient un produit, contient

l’un des deux facteurs. Ceci est encore équivalent à l'intégrité de l’anneau quotient Z/pZ. La réci- proque est fausse, avec 0Z (idéal premier) et 0 (nombre non premier).

3. alc,blcaAb=1—= able.

Question du jury : 1. Deux candidats au CAPES se présentent devant le même jury. Le premier, qui a la tête haute, compte les membres du jury et affirme que leur nombre ne divise pas 7. Le second (moins sur de lui) compte les jambes de ses «bourreaux» attablés et affirme que le nombre obtenu est un multiple de 7. Est-ce possible ?

2. Peut-on relever le défi suivant : écrire en base 10 un carré parfait (N = n?) avec exactement 10 chiffres 0, 10 chiffres 1 et 10 chiffres 2.

3. Existe-t-il une factorielle à 5 zéros exactement dans son écriture décimale ?

Réponse :

1. Soit n > 1 le nombre de membres du jury. On a 7 | 2n et 2 A 7 — 1 donc, par le lemme de Gauss, 7 | n.

2. Si N convient, on à 3 | N car la somme des chiffres de N est 30 € 3Z. Par le lemme d'Euclide, 3 | n. Ainsi, 9 | n?, ce qui est impossible puisque 30 & 9Z.

3. Si n! convient, 10° | n! donc 5° | n!, donc n > 24 puisque 24! ne contient que 4 facteurs 5 à pêcher dans 5, 10, 15 et 20. D'autre part, pour n > 25, n! contient au moins 6 facteurs 5 puisque 25 — 52. Avec en plus au moins 6 facteurs 2, puisque 25 À 56 — 1, n! est divisible par 106 et se termine donc par au moins 6 zéros.

Exercice 28 : Pour a,b € N, pgcd(a, b) = 1 si, et seulement si, pgcd(a + b, ab) = 1.

Exercice 29 : (Nombres de Fermat et infinité de nombres premiers par Pélya) Les nombres de Fermat sont définis par F, = 2? +1oùneN. 1. Montrer que, pour n,k EN, F, divise F3% — 2. 2. En déduire, en considérant un diviseur g commun de F, et F4, que F À Fix = 1!.

3. Conclure que les nombres premiers sont en nombre infini.

Propriété : (Caractérisation du ppcm) Soit a, b € N, non tous deux nuls et m € N. On envisage les énoncés :

i) a] m,b|m et, pour tout multiple 4 commun de a et b, m |.

ii) m est le ppcm de a et b, ï.e le plus petit élément de M, 4 pour <. 1. Onai) = ü). 2. Si, de plus, d est le pgcd de a et b, alors ab = dm. 3. Onaü) = à).

1Variante : Considérer un diviseur premier p (cf infra) commun à F, et à Fn4x, et aboutir à une contradiction avec

les deux congruences 22" = —1 (p) et D (ay = —1 (p).

16

Arithmétique dans Z

Preuve : L'’implication 4) — ti) vient du fait que deux entiers naturels rangés dans un ordre pour la divisibilité sont rangés dans le même ordre pour <.

On relie à présent m — ppem(a, b) et d — pgcd(a, b). Soit a’,b' € N tels que a = da’, b = db’ et a Ab! = 1. On montre que m = da'b' (grâce à ) — ii)) de sorte que md = da'b' d = ab. Soit y un multiple commun de a et b. On écrit

u=aa=bf = da'a = db'3 donc a/a=b'B.

Puisque a’ Ab’ — 1, par le lemme de Gauss : a’ | 8. Avec des notations évidentes, 8 = a/c donc n = db! B = db! a’c, da'b' | u. Enfin, da/b' = ab! — a’b est multiple commun de a et b, ce qui donne m = da’b'.

Si on suppose maintenant que m est le plus petit élément de M4, on à clairement a | m et b| m. Pourquoi m divise-t-il tout multiple commun y de a et b? On reprend ce qui précède et on conclut.

Propriété :

Soit n EN, n £ 0. Pour k € N, on a les équivalences : 1. Il existe / € Z (et même dans N) tel que {k = 1 (n). 2. Les entiers k et n sont premiers entre eux. 3. VxeZ, 20<L<n-—1,x=Lki(n).

POUR ALLER PLUS LOIN : Les éléments inversibles de (Z/nZ, +, x) sont exactement 1. les classes de congruences k, avec 0<k<n—-1letkAn—=l. 2. les classes £ qui engendrent le groupe additif (Z/nZ, +).

Aussi, si p est premier, alors tout élément non nul de l’anneau Z/pZ est inversible :

Z/pZ est un corps, en particulier est un anneau intègre.

4.3 Une équation diophantienne incontournable

Un champs (très grand) est modélisé par le plan qu’on munit d’un repère (©, 4, j). En chaque point à coordonnées entières autre que ©, est posté un chasseur. On suppose que les chasseurs ne tirent qu "à la verticale. Question du jury : Un oiseau part de O et vole en ligne droite. Peut-on lui trouver une trajectoire rectiligne salutaire ?

Un oiseau vole selon la droite À d’équation ax + by = c où a,b € Z sont non nuls et c € Z. Que se passe-t-il ?

Le problème posé est la résolution dans Z? de l'équation € : ax +by = c d’inconnues #,y € Z.

Pas 1 : L'égalité ax + by = c fait penser à la relation de Bézout. Aussi, on introduit «naturellement» le pgcd d de a et b. Il existe alors a/,b" € Z? premiers entre eux tels que a = da” et b = db'. Pour (x,y) € Z?, ax + by = c = dax + db'y = c = d | c donc la condition d | c est nécessaire à l’existence de solutions pour €. Par exemple, la droite d’équation 3x + 6y = 5 est une bonne trajectoire pour l'oiseau.

On suppose désormais que d = pgcd(a, b) divise c, ce qui ramène le problème à la résolution dans Z? de l'équation (encore notée €) ax + by = c avec a Ab = 1.

17

Arithmétique dans Z

pas 2 : Par le théorème de Bézout, il existe (u,v) € Z? tels que au + bu — 1 donc auc + bvc = c, donc Moto = UC, yo = ve) est une solution particulière de €.

Pas 3 : Pour (x,y) € Z? et M(x,y), ax + by = c si, et seulement si, ax + by = axo + byo, ou encore a(x — x) = —b(y — yo). Géométriquement, ax + by = c revient à dire successivement que M € À, que MM est un vecteur directeur de À dont un vecteur directeur notoire est ü (—b, a).

Si (x, y) est solution de €, b | a(x — x9) avec a À b — 1 donc, par le lemme de Gauss, il existe k € Z tel que æ — x0 = kb, x = x0 + kb. Par substitution, il vient y — yo = —ka, y = yo — ka. Réciproquement, tout couple (0 + kb, yo — ka) avec k € Z est solution de €.

Exercice 30 : Donner les solutions entières de 504% + 1188y = 144.

Autre vision de l’affaire : Si (x, y) est une solution de €, on a ax = c(b) (ou ax = € dans Z/bZ) et by = c(a). On ramène donc l’équation € au système de congruences

Puisque a et b sont premiers entre eux, il existe u, v € Z tels que ua + vb = 1; donc 1. ua = 1 (b) ou, en langage savant, & est l'inverse de a dans Z/bZ. 2. vb=1(a).

Ainsi, ua x = uc(b), ce qui assure l'existence de k € Z tel que x = uc + kb. Le même travail modulo a donne :

HE Z, y = ve+la. Puique ax + by = c, il vient a(uc + kb) + b(uc+ la) = c donc c{ua + vb — 1) + ab(k +1) = 0, ab(k +1) —0, k = —l puisque a Z 0 et b Æ 0. Réciproquement, tout couple (uc + kb, uc — ka) est solution de €.

Exercice 31 : Travailler plus …

Un enseignant donne des cours particuliers de mathématiques sur 27 semaines à raison de 35 heures par semaine. Il travaille avec 2 types d'élèves : les élèves de terminale $ nécessitent 15 heures de cours individuels pour se remettre au niveau alors que les élèves de première $S 18 heures. Le prix horaire est de 25 euros pour un élève de terminale et 30 euros pour un élève de première. Quelle est la somme maximale perçue par l'enseignant ?

Corrigé : Si x et y désignent le nombre d'élèves de TS et de 1$, on a 15x + 18y = 27 x 35 = 3 x 315 donc 5x + 6y = 315 (E).

Pour (x,y) solution de (Æ), modulo 6, 5x = 315 (6), —x = 6 x 52 +3 = 3 (6), x = —3 = 3 (6). Ainsi, avec la contrainte 15x < 27 X 35 — 945, on a x € {3;9; 15; 21; 27; 33; 39:45:51; 57:63}. Pour trouver le bon y correspon- dant, on peut réduire (ÆE) modulo 5 : 6y = y = 0 (5) et, avec la contrainte 18 x y < 945, on a y € {0:5;--.;50}. Réciproquement, (3; 50), (9; 45), (15; 40), (21; 35), (27; 30), (33; 25), (39; 20), (45; 15), (51: 10), (57; 5) et (63; 0) sont solutions de (Æ). Le revenu maximal est 3 x 15 x 25 + 50 x 18 x 30 euros.

5 Quelques joyaux de la reine

5.1 Décomposition en facteurs premiers

Commentaire : Lorsqu'on casse 60 jusqu'à «une» décomposition en nombres premiers, on peut commencer par 60 = 6 x 10 ou 60 = 4 x 15 ou ---, et on sait, par expérience, qu’en continuant le procédé, on obtiendra

une décomposition achevée indépendante des choix initiaux effectués. Gauss dit : «on suppose à tort tacitement que cette décomposition ne soit possible que d’une seule manière.»

18

Arithmétique dans Z

Théorème : (Théorème fondamental de l’arithmétique)

Tout entier n > 2 peut s’écrire comme un produit de facteurs premiers, et ce, de façon unique (à l’ordre près des facteurs).

Exercice 32 : On note V36Z l’ensemble {x € Z \ n € N*, x" € 36Z}. Montrer que 6Z € V36Z et, par contraposée, V36Z € 6Z. Que vaut V11Z?

Exercice 33 : Montrer que (n,m) + 2"(2" +1) — 1 est une bijection entre N x N et N.

Exercice 34 : Montrer qu'il y à au moins autant de nombres irrationnels que de nombres premiers. On pourra considérer ,/p pour p premier.

Question du jury : 1. Donner des nombres irrationnels célèbres.

2. Peut-on mesurer autrement l'encombrement des nombres irrationnels dans R ?

Réponse : 1. Les nombres 7 (J.H Lambert, 1761) et e (Euler) sont des irrationnels notoires.

2. R\Q est une partie dense de R (topologie) et non dénombrable.

5.2 Petit théorème de Fermat

Théorème : (Petit théorème de Fermat énoncé en 1640, démontré par Euler en 1736)

Pour p premier et a € Z, on a : a? = a (p). Si p ne divise pas a, la congruence de Fermat devient :

alt= 1(p).

Preuve : Pour a A p = 1, on note Il, la multiplication par « modulo p. Avec le lemme de Gauss, on montre : Vk,k' € [,p — 1]],k # &’ ka £ k'a(p),

ce qui fait de IT, , une injection et donc une permutation de Z/pZ. On a alors (p — 1)! = a2a...(p — 1)a d'où : (aP=1 — 1)(p — 1)! = 0 (p). Par ailleurs, le nombre premier p ne divise aucun des facteurs de (p — 1)! donc est premier avec (p — 1)!. Il vient, toujours avec le lemme de Gauss, a?! = 1 (p).

Exercice 35 : (Une autre preuve) Soit p un nombre premier.

1. Pour 1 <k < p —1, p divise le coefficient binomial [ets 2. Pour a, be Z, (a+ b)? = aP + bP (p).

3. Par récurrence sur a € N, a = a (p).

Question du jury : Vrai ou faux : Le nombre a — 302% + 239%0 n’est pas un nombre premier.

Réponse : On réduit a modulo 31.

5 3

Exercice 36 : Soit n > 2. On pose a = n° — n. Montrer que n° — n | a puis que 30 | a.

Corrigé : D’après le petit théorème de Fermat, 5 | aet, avec a = n(n4—1) = n(n?—1)(n?+1) = (n°-n)(n?+1), 3 | a. Puisque 3 et 5 sont premiers entre eux, 15 | a. Enfin, a = n(n — 1) (n + 1)(n? + 1) où n et n — 1 sont des entiers consécutifs, donc 2 | a. On conclut que 30 | a puisque 2 et 15 sont premiers entre eux.

19

Arithmétique dans Z

æercice : Pour n,m mn(m°° — n°°) n’est pas premier. E, 37:P mEeN, cu 0 t pas p

Corrigé : On écrit mn(m°0 — n°0) = m£ln — mn£l = (m

Fermat, 61 | mn(m0 — n60).

61

mn — m(n n) et, avec le petit théorème de

Exercice 38 : On considère la suite définie pour n > 1 par ay = 2° +3" +6" — 1. Montrer que tout nombre premier divise au moins l’un des a».

Corrigé : On a a2 — 48 donc 2 et 3 divisent a. Pour p > 5 premier, on évalue 6a,_2 et on conclut avec le petit théorème de Fermat.

5.3 Théorème de Wilson

Théorème : (Théorème de Wilson)

Pour p € N, p est premier si, et seulement si, (p — 1)! = —1 (p).

Preuve : On envisage sur (Z/pZ)" la relation d ‘équivalence rRysyef{x,z ‘}.

Quelles sont les classes réduites à un singleton? On a: x = x l(p) & x? =1& (x —1)(x +1) = 0, et par intégrité de Z/pZ, x = 1 ou x = —1 = p—1. Ainsi, en regroupant les facteurs par classe dans le produit (p—1)!, ona:(p—1)! = —-1(p).

Exercice 39 : (Euclide pour modèle)

Commentaire : Les nombres premiers strictement plus grands que 2, qui sont en quantité infinie d’après Euclide, sont tous impairs, donc de la forme 2k +1, k € N*. Plus généralement, existe-t-il des nombres premiers dans une suite ak +b? La première remarque (facile à vérifier) est que, si tel est le cas, les coefficients a et b sont nécessairement premiers entre eux. Le théorème de la progression arithmétique, dû à Dirichlet, affirme que, si a \b= 1, alors il existe une infinité de nombres premiers congrus à b modulo a.

Soit p > 2 premier. — 1 1. Vérifier que À € N. p—1l

2. Donner les congruences possibles de » modulo 4. Dans chaque cas, préciser la parité de £—.

3. (a) On suppose que p = 1 (4). Montrer que VI < k < PB, PB +k= PT + (k— 1) (p). En déduire, avec la congruence de Wilson, que —1 est un carré modulo 4.

(b) On suppose que p = 3(4). Montrer que —1 n’est pas un carré modulo p. On pourra raisonner par l'absurde (en écrivant —1 = x? (p), x € Z) et obtenir une contradiction en évaluant +?! modulo p.

4. Pour montrer qu'il existe une infinité de nombres premiers de la forme 4k + 1, on raisonne par l'absurde en envisageant la liste {p1,--- ,pA} des nombres premiers congrus à 1 modulo 4. On pose

M = A(pi pa) +1.

(a) Pourquoi M n'est-il pas premier ? (b) Soit p un diviseur premier de M. Vérifier que p £ 2, puis que p = 1 (4). (c) Pourquoi —1 est-il un carré modulo 4? Conclure.

5. Pour montrer qu’il existe une infinité de nombres premiers de la forme 4k+3, on raisonne par l’absurde en

envisageant la liste {p1,--: ,pA} des nombres premiers congrus à 3 modulo 4. On pose M = 4p1 ---pn—1.

(a) Pourquoi M n'est-il pas premier ? (b) A-t-on : 2| M?

(c) Pourquoi M possède-t-il au moins un diviseur premier congru à 3 modulo 4?

)

(d) Soit p un tel diviseur premier de M. Pourquoi a-t-on : p > p, ? Conclure.

20

Arithmétique dans Z

6 Pour aller plus loin

RÉFÉRENCE : Cours d’algèbre, chapitre 2, D. Perrin, collection de l'ENS des Jeunes Filles, 1994.

L'arithmétique est l’étude de la divisibilité et on peut parler de divisibilité et de diviseurs dès qu’on est en présence d’un anneau. Soit donc Z un anneau, commutatif (pour éviter les diviseurs à gauche … en sortant de l'ascenseur), unitaire (i.e possédant un neutre 1 pour la multiplication) et non nul (1 0). On rappelle que la relation binaire | est réflexive et transitive.

6.1 Éléments marginaux de Z

Deux types d'éléments de Z sont «marginaux» pour la divisibilité :

1. le neutre 0 de l’addition puisque a | 0 pour tout a de Z. Pour a £ 0, on a toujours a x 0 — 0 et, si de plus ab — 0 avec b 0, on dit que a et b sont des diviseurs (sous-entendu «spéciaux») de 0. En particulier, tout nilpotent non nul (comme 2 dans Z/8Z) est un diviseur de 0.

2. les inversibles ou les unités de Z dont l’ensemble-groupe est noté U(Z).

(a) Une unité u divise tout a € Z puisque a=uu la.

On dit que u est un diviseur trivial de a.

(b) Sia,d,m € Z et si u € U(Z), alors d| a & d| ua et m € aZ & m € uaZ de sorte que les ensembles D, des diviseurs de a et aZ des multiples de a coincident, pour toute unité u, avec D, et uaZ.

Exemple :

(a) Les entiers 1 et —1 sont des inversibles de Z. Si x £ 0 vérifie | x [> 1, alors x? =| x [?> 1 donc les inversibles de Z sont exactement 1 et —1.

(b) Si Z est l'anneau Zi] de Gauss, U(Z) est le groupe {1,i, —1, —-i} des racines quatrièmes de 1 dans C. En effet, pour u = m +in € Z, on a les équivalences :

- uEU(Z) — 4(p,9) € Z? 1 = (mp — ng) + i(np + mg) _ 1 = — — 2(p,q) € Faune) (système linéaire aux inconnues p et q, de déterminant m°?+n?) 0 = np + mq rs €EZLet 5%: € Z (formules de Cramer)

— m2 +n? = 1. (c) Si P est un polynôme constant de Z[X] avec P = a € U(Z), alors P est inversible (et PT est le

polynôme constant a _!). La réciproque est fausse sans qualité supplémentaire de l'anneau Z; Dans Z/8Z|X], le polynôme non constant 1 — 2X est inversible puisque

(1—2X)(1+2X +2X7)=1-28X3 = 1 8X$ — 1.

Exercice 40 : 1. Si a est nilpotent, alors 1 — a est inversible et (1 — a)! =1+a+:..+a"1 dès que a" = 0. 2. (a) Pour 1 idéal de Z, on a les équivalences : i. Î=2Z ü. 1ET ii. 1 N U(Z) #0. (b) Un corps commutatif n’a que deux idéaux : 0Z = {0} et 1Z = Z.

21

Arithmétique dans Z

6.2 Eléments associés

Afin de réduire une surprésence des unités de Z et traduire leur caractère négligeable pour |, on définit une relation d'équivalence sur Z en posant

aTbe& ue U(Z) b = ua.

On dit alors que a et b, égaux à un inversible près, sont associés. La classe de 0 est Ü — {0} et celle de 1 est 1 = U(Z). On fait «descendre» | sur l’espace quotient, de façon à raisonner sur les «types» d ‘éléments comme on raisonne sur les éléments : Si a © a/,b © b’ et a | b, alors a’ | b’ donc la relation | de divisibilité passe bien au quotient Z/ © qu’on note (sans surprise) NW. La relation induite sur les classes, encore notée | et encore appelée divisibilité, est aussi réflexive et transitive.

6.3 Éléments indivisibles

On cherche dans l’anneau Z les éléments «indivisibles». On peut formaliser cette notion de deux façons, selon qu’on se place au niveau «moins 1» des diviseurs ou à l'étage «plus 1» des multiples :

1. il y a les insécables ou les atomes.

2. il y a les «casse-casse propre», les éléments qui, lorsqu'ils divisent, divisent sans se répandre, de façon solidaire.

Définition : 1. Un élément a de Z est dit irréductible s’il est non marginal et à diviseurs triviaux :

aZ0, agU(Z) et les diviseurs de a sont exactement les unités et les associés ou de façon équivalente : a£0, aŒgU(Z), VbceZ a=bc=beU(Z)ouceU(Z). 2. Un élément a de Z est dit premier s'il est non marginal et s’il a la Gauss-attitude :

af£0, agU(Z), Vb,ceZ albc—=alboualc.

Exercice 41 :

1. Dans Z/6Z, l'élément 2, non nul et non inversible puisque diviseur de 0 (2 x 3 — 0), est non irréductible puisque 2 = 2 x 4 avec 4 non inversible (4 x 3 — 0). En revanche, 2 est premier. En effet, si b et c ne sont pas multiples de 2, b et c appartiennent à {1,3,5} donc bc € {1,3,5}, ce qui montre bc n’est pas non plus un multiple de 2.

2. Dans Z[iV5], on pose, pour z = a +iv5b, N(z) = 22 = a? + 5b? et on vérifie que N(zz') = N(z)N(z/). Si 2+4iv5 = z22!, alors N(z:) est un diviseur de N(2 + iV5) = 9. Or les équations (en (a,b) € Z?) a? + 5b? = 1, a? + 5b? = 3 et a? + 5b? = 9 ont leurs solutions dans {(1,0),(—1,0), (*2,* 1)}. Seuls les candidats *(2—i/5) ne sont pas des diviseurs effectifs de 2+i45 (Pas de solution dans Z? pour le système

2a + 5b = 2 = { : ! Dh à Ceci montre que z diviseur de 2+ 55 est soit inversible, soit associé à 2+5V5 :2+iVv5 = = est irréductible. De même, on montre que 3 est irréductible. Avec (2+iV5)(2—45) = 9, le non marginal 2 + iv5 divise 3 x 3 sans pour autant diviser l’irréductible 3. Ainsi, l’irréductible 2 + iÿ5 n’est pas

premier.

22

Arithmétique dans Z

6.4 Notions de pgcd et ppcm

Alors que l’objet d'étude est un anneau Z, les «bons» sous-objets sont les idéaux monogènes ou principaux de Z : la phrase a | b se traduit par bZ C aZ. On a les définitions : Définition : Pour X C Z, on dit que X a un pgcd si {xZ, x € X} admet une borne supérieur dans l’ensemble ordonné (I(Z), C ) des idéaux principaux de Z. Dans ce cas, tout d € Z qui vérifie dZ = sup æZ est appelé pgcd

zEeX de X.

Justification de la terminologie : Si X — {a,b} admet un pgcd, alors d € Z est un pgcd de a et b si, et seulement si, d | a, d | b et, pour Ô dans Z, à divise d si à est un diviseur commun de a et b.

Définition :

Pour X € Z, on dit que X à un ppem si {xZ, x € X} admet une borne inférieure dans l’ensemble ordonné

(I(Z), C ) des idéaux principaux de Z. Dans ce cas, tout m € Z qui vérifie mZ = inf xZ est appelé ppem €

de X.

Remarque : Si X — {a,b} admet un ppem, alors m € Z est un ppem de a et b si, et seulement si, a | m, b| m et, pour u dans Z, m divise y si u est un multiple commun de a et b.

6.5 Anneaux intègres

i) Relation d ‘ordre

Il manque à la relation | une qualité pour en faire une brave relation d'ordre et ainsi assurer le même statut d° ensembles ordonnés à (W,|) et à (I(Z), € ). Ceci amène à supposer Z intègre, c-à-d sans diviseurs de 0.

Propriété :

1. La relation de divisibilité est une relation d ‘ordre sur W. Pour |, NW admet un plus petit élément (1 = U(Z)) et un plus grand élément 0 = {0}.

2. Pour a,b € Z, aZ = b£Z si, et seulement si, à — b, ou de façon équivalente, a et b sont associés. Aussi, pour À C Z admettant un pgcd, a et b sont des pgcd de X si, et seulement si, a et b sont associés.

3. Pour a € Z, on a les équivalences :

(a) a est irréductible.

(b) à est minimal dans W \ {0,1}.

(c) aZ est maximal dans l’ensemble II(Z) \ {1} des idéaux propres principaux de Z. 4. Tout élément a premier de Z est irréductible.

5. Pour a, b € Z, sous réserve d ‘existence de pgcd de {a,b}, tout représentant de la classe borne inférieure de {ä,b} dans (W,|) est un pgcd de {a,b}. Si d est un tel représentant, On dit que d est le pgcd de a et b.

23

Arithmétique dans Z

ii) Caractère héréditaire de l’intégrité

À un anneau Z, sont naturellement attachés

— l’anneau des polynômes Z[X],

— les anneaux quotients Z/I où I est un idéal de Z. Quand Z a une qualité, on veut savoir si cette qualité est héréditaire, i.e. si elle passe à Z[XT et à Z/I. Par exemple, la commutativité de Z est transmise. On suppose que l’anneau Z est intègre.

Intégrité de Z et Z[X] : On introduit 1. l'application degré de Z [X] dans NU {—co} avec d°0) = —co. Selon les conventions usuelles de calculs, pour Pi, P2 € Z[X],on a d'(Pi + P2) < d°(P1) + d°(P2) et, grâce à l'intégrité de Z, d’(PiP2) = d’(P1) + d°(P). 2. l’application valuation de Z[X] dans N U {+o} avec v(0) — +oo. Selon les conventions usuelles de calculs, pour P;, P € Z[X], on a v(P; + P:) > v(P;) + v(P2) et, grâce à l'intégrité de Z, v(P; P2) = v(P;) + v(P)).

Sous l'hypothèse «Z intègre», avec le degré, on caractérise les éléments inversibles de l’anneau Z]X] comme les polynômes constants de terme constant inversible dans Z. Avec l’application valuation, on montre que Z[X] est aussi intègre et, en définitive, Z est intègre si, et seulement si, Z[X] est intègre.

Exercice 42 : (Toujours avec le degré) Soit Z un anneau. 1. Poura€e Z, P(a)=0&X-—-al|P. 2. On suppose que l’anneau Z est intègre. (a) Les polynomes de Z[X] de degré 1 sont des éléments irréductibles. (b) Quelle propriété du corps € permet d'affirmer que les irréductibles de C[X] sont exactement les

polynômes de degré 1?

Intégrité de Z et Z/I :

L'’anneau Z des entiers relatifs est intègre alors que Z/6Z ne l’est pas comme le montre la relation 2.3 = 0. Ceci amène à la notion d'’idéal premier.

Définition :

Un idéal 1 de Z est dit premier si I est propre (1 Æ Z) et si V(a,b) € Z, abdE l=a€eloubel.

Propriété :

Soit Z un anneau et 1 un idéal de Z. Les propositions suivantes sont équivalentes :

1. L’anneau Z/I est intègre.

2. L'idéal Z est premier.

Parmi les anneaux intègres, se distinguent les corps. Quels sont les idéaux (premiers) 7 de Z tels que Z/I est un Corps ?

24

Arithmétique dans Z

Définition : Un idéal I de Z est dit maximal si I est propre (1 Æ Z) et si I est un élément maximal pour l'inclusion dans l’ensemble TZ des idéaux propres de Z :

TZ Z et, pour tout JET, I C J = I—J.

Propriété :

Soit Z un anneau et 1 un idéal de Z. Les propositions suivantes sont équivalentes : 1. L'’anneau Z/I est un corps.

2. L'idéal Z est maximal.

6.6 Anneaux principaux

Quand on fait de l’arithmétique sur l’objet Z, les «bons» sous-objets sont les idéaux (et non les sous- anneaux) de Z. Il est naturel d'espérer une correspondance Arithmétique-Algèbre 0 : a + aZ de Z vers l’ensemble Z(Z) des idéaux de Z. Il y à deux obstructions à la mise en place d'un dictionnaire efficace :

1. @ n’est pas injective. Ce problème est résolu si on suppose que Z est intègre et si on considère W au lieu de Z. L'application à + aZ, correctement définie, est alors strictement décroissante de (W,|) dans (Z(Z), C).

2. bn'’est pas surjective puisqu ‘il y a, à priori, plus d'’idéaux que d'’idéaux principaux.

Ceci amène à supposer que l'anneau Z, supposé intègre, n ‘a que des idéaux principaux : H(Z) = Z(Z). On dit alors que Z est un anneau principal.

6.6.1 Entre les anneaux euclidiens …

Définition : Soit Z un anneau commutatif unitaire non nul. On dit que Z est un anneau euclidien si Z est intègre et si Z est muni d’une application 0 : Z* = Z \ {0} — N vérifiant :

1. Va,be Z* 6(a) < 6(ab).

2. Pour (a,b) € Z x Z*, il existe (q,r) € Z? tels que (a) a=bg+r: (b) r =0 ou (r Z0 et ô(r) < 6(b)).

Autrement dit, un anneau euclidien est un anneau intègre Z possédant une division et une application croissante sur Z* qui mesure les restes.

Propriété :

Tout anneau euclidien est un anneau principal.

Pour la culture : Il existe des anneaux principaux non euclidiens : Z | Hi] , RIX,Y]/(X?2 +Y2 +1).

6.6.2 et les anneaux factoriels, …

Le caractère principal de Z agit comme le double effet «Kiss Cool» …

25

Arithmétique dans Z

i) Existence d ‘une décomposition en facteurs irréductibles

Propriété : (Remontée infinie de Fermat)

Si Z est un anneau principal, alors

1. toute suite croissante (1,) d’idéaux de Z est stationnaire.

2. tout ensemble € non vide d’idéaux de Z a un élément maximal pour l’inclusion.

Remarque : Considérer une suite croissante d'’idéaux monogènes revient à considérer une suite décroissante de diviseurs et, dans l’anneau Z des entiers relatifs qu ‘on ramène à N, c’est le bon ordre qui justifie le caractère stationnaire.

Preuve :

1. Considérer J = (J 7h, vérifier que J est un idéal de Z, soit un certain (a) = aZ. Il existe alors N € N neN tel que a € In, puis, pourn > N,1, = IN =. 2. Si€ n°a pas d’élément maximal, soit 1, dans €. L'ensemble des idéaux contenant 1, est non vide et non réduit à {6 puisque /9 n’est pas maximal, donc on envisage 7 dans € qui contient strictement 15, puis lL € € qui contient strictement /, etc ... Ainsi, on construit une suite strictement croissante d idéaux de Z, ce qui est absurde.

Corollaire : Soit Z un anneau principal.

1. Tout élément non marginal + de Z admet un diviseur irréductible.

2. Tout élément non marginal x de Z admet une décomposition en produit de facteurs irréductibles.

Preuve :

1. Considérer l’ensemble £ des idéaux propres de Z qui contiennent x, non vide puisque xZ € €. Envisager ensuite un élément maximal 7 de €, un certain 7 = yZ, et vérifier que y | x et que y est irréductible.

2. On écrit à bon droit to = x = æ1y1 avec y1 irréductible. Si x, est une unité, on conclut. Sinon, +1 = æ2y2 avec y2 irréductible. Dans cette construction pas à pas, on à une suite croissante (x,Z) d'idéaux de Z. Ainsi, il y à arrêt du processus, fin de la dichotomie, c-à-d l'existence de N € N tel que xn EU(£Z).Il vient To = TZ =ZÆN Y1:--yN où chaque y; est irréductible.

ii) Unicité de la décomposition

Propriété :

Si Z est un anneau principal, tout élément a irréductible (non marginal à diviseurs triviaux) de Z est premier (non marginal à la Gauss-attitude). Ainsi, dans Z principal, on a les équivalences :

1. a est irréductible. . a est premier non nul.

2 3. aZ est non nul et maximal. 4

. aZ est non nul et premier.

Preuve : Si a est irréductible, (a) = aZ est maximal pour l'inclusion dans l’ensemble des idéaux pricipaux propres de Z, donc dans l’ensemble des idéaux propres de Z. Ainsi, aZ est premier et a 3 0 est premier.

26

Arithmétique dans Z

Corollaire :

Si Z est un anneau principal, alors tout élément non marginal x admet une décomposition en produit de facteurs irréductibles, unique à l’ordre près des facteurs et à des facteurs inversibles près. On dit que Z est un anneau factoriel.

Preuve : On suppose que z = a1---a; et x = b1-:-b, où a, ..., &r, b1, ... b, sont irréductibles. On raisonne par récurrence sur n = min(r,s). Sin = 1, x est irréductible et x = a1 = bi, r = s = 1. On suppose la propriété vraie au rang n — 1. L'élément premier a; divise le produit b; ---b, donc divise (quitte à échanger les indices l’irréductible b1 : a = ub1 avec u € U(Z). Par intégrité de Z, on a a2---a, = b2-:-b, à un inversible près. La récurrence s ‘enclenche et donne r = 5, a; = b; à un inversible près.

Pour la culture : On admet que

1. le caractère principal ne passe pas aux anneaux de polynômes. On peut avoir en tête le résulat éclairant : Z[X] est principal si, et seulement si, Z est un corps.

2. le caractère factoriel passe aux anneaux de polynômes : si Z est factoriel, alors Z[X1] l’est aussi. Il existe des anneaux factoriels non principaux : Z[XT, RIX, Y] = RIX][Y] …

ii) Les objets pgcd et ppcm dans un anneau factoriel

Si Z est un anneau factoriel, on choisit un et un seul élément dans chaque classe (modulo la relation «être associé») d’irréductibles et forme une partie P de Z. Dans Z, on choisit l’ensemble {2,3,5,7,11,13,17,---} des entiers naturels irréductibles (nombres premiers). Pour tout x € Z non nul, on a la décomposition en facteurs irréductibles :

T=Uu Il pr), uEU(Z), où la famille dans N (v,(x)),ep est presque nulle. pEP

Par unicité de la décomposition,

Vp € F3 Vx,y € Z, T F 0, y F 0, Up(TY) — Up(T) + Up(y),

puis z|ye VpEP, w(r) < w(y), puis T+yÆO0—VPEP, vx +y) > min(v,(x),v(y). Soient 21,%2,::: ,Æn (n > 1) des éléments non nuls de Z. La partie X = {x1,--: ,x,} de Z admet un pgcd et

un ppcm et

l.d= [Er (GG) vtr) est un pgcd de X, pEP

2. m= I] pr) v%(2)) est un ppem de X. pEP

6.6.3 le principal, c’est Bézout.

Dans l’anneau (factoriel) Z[X], on peut se convaincre que pgcd(2, X) = 1 alors qu’il est impossible d ‘écrire 1=2P +xQ avec P,Q € Z[X].

Théorème de Bézout dans un anneau principal :

Soit Z un anneau principal. Pour a1,:-- ,a, dans Z, on a les équivalences : 1. &1,..., a, Sont premiers entre eux : pgcd(a1,::: , an) = 1. 2. a1,..., an sont «Bézout» entre eux : 1À1,--:, An € Z, Aa +: + ÂnGn = 1.

27

Arithmétique dans Z

Preuve : On suppose que a1, ..., 4n Sont «Bézout» entre eux. L'idéal (a1,-:- ,an) = (ai) +:-:+ (ar) est Z = (1) donc est principal. I contient chaque (a;) donc est un majorant de {(a1),--- ,(a,)}. Enfin, si Z est un majorant dans I(Z) de {(a1),:-: ,(a,)}, ? contient 1 et coïncide donc avec Z. On a montré que {(a1),--: ,(an)} admet un sup dans I(Z), qui est Z, donc pgcd(ai,-:- ,an) — 1. Pour l’autre implication, comme Z est principal, l’ensemble II(Z) des idéaux principaux de Z est l’ensembleZ(Z) de tous les idéaux de Z. Aussi, le sup((ai),--: ,(an)) pris dans I(Z) (qui vaut Z puisque pgcd(a1,--- ,an) — 1) est ici sup((ai),--- ,(an)) pris dans Z(Z) (qui existe toujours et vaut (a1,--: ,an) = (ai) +---+(a,). Ainsi, (a) ++: + (an) = Z

Corollaire : (Théorème de Gauss)

Si Z est un anneau principal, à, b,c € Z, alors

albcetafAb=1—=alc.

28