ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

L'arithmétique de Gauss        Congruences , Distribution des nombres premiers
   
  Outre les exercices présents sur cette page, voir aussi les pages exos LYC, SUP

Une des contributions majeures de Gauss en mathématiques sera dans ses Recherches arithmétiques (Disquisitiones arithmeticae, 1801, disponibles en français sur Gallica (traduction de A.-C.-M. Poullet-Delisle,1807) où il crée une théorie arithmétique nouvelle avec le concept de congruence en énonçant des résultats et théorèmes fondamentaux.

Il faut cependant noter que le concept implicite de congruence apparaît déjà en Grèce avec Diophante d'Alexandrie et en Inde avec Brahamagupta. On le retrouvera aussi dans la mathématique chinoise du 13è siècle avec Qin Jiushao (1202-1261) qui écrivit un Traité de Mathématiques en Neuf Chapitres, à l'instar de celui du même nom au 1er siècle après J.-C.

L'intervention des structures algébriques, avec l'anneau Z/nZ des entiers modulo n et l'étude des corps de nombres algébriques permettent de parler de théorie algébrique des nombres.

L'introduction de l'analyse en théorie des nombres, principalement dans l'étude de la distribution des nombres premiers, sera encore le fait de Gauss mais aussi de Euler qui, avant lui, "découvrit" les célèbres fonctions zeta : on parle là de théorie analytique des nombres. Une théorie qui nous entraîne au cœur des mathématiques les plus difficiles avec l'hypothèse de Riemann, loin de l'arithmétique classique des entiers naturels de Pythagore, Euclide ou Nicomaque.

Une autre branche de l'arithmétique est la théorie additive des nombres, étudiant la décomposition d'un entier en somme d'entiers pairs, impairs, premiers ou de puissances de tels nombres. Elle naît avec Pythagore et son célèbre théorème; on la rencontre au cours des siècles avec Diophante, Goldbach, Waring et Lagrange par exemple et jusqu'à nos jours où elle se mêle à la théorie analytique comme le montre la preuve du grand théorème de Fermat ou encore la conjecture de , l'étude des nombres premiers jumeaux et plus généralement des nombres premiers en progression arithmétique.

La théorie des congruences :

Si a, b et p désignent des entiers relatifs on écrit a ≡ b  [p] pour signifier que a - b est un multiple de p.

On dit que a est congru à b modulo p. L'entier p est le module de la congruence. On doit à Gauss, dans cet ouvrage, ce signe des congruences arithmétiques.

Les écritures  a ≡ b  (p) ou a ≡ b  (mod. p) se rencontrent également. On vérifiera facilement cette première proposition :

a ≡ b  [p] si et seulement si a et b ont même reste dans la division euclidienne par p.

La relation est une relation d'équivalence. L'ensemble des classes d'équivalence constitue l'anneau des classes résiduelles modulo p.

  Un résultat trivial mais fondamental :  dans le cas où a et b sont éléments de N, b étant non nul, soit r le reste de la division euclidienne de l'entier a par l'entier b : on a l'égalité a = bq + r où q est le quotient et r le reste de la division avec 0 r < b. Dans ces conditions : a ≡ r  [b]. La réciproque de ce résultat est valide à condition de bien imposer la condition 0 r < b. On dira que r est le résidu de a modulo p.

On montrera sans difficulté que :

L'arithmétique des congruences, on parle depuis peu d'arithmétique modulaire est un outil puissant dans la résolution des équations en nombres entiers et, plus généralement, en théorie des nombres, comme par exemple, dans l'étude de la distribution des nombres premiers et les progressions arithmétiques de tels nombres.

Programme en ligne de calculs de congruences modulo p :

Petits exos avec indications ou solution :

  1. Montrer que le carré de tout entier naturel non multiple de 5 est congru à  ± 1 modulo 5.
    Rép :
    très simple...

  2. La preuve par 9 des écoliers :   Adam Riese

  3. Déterminer les entiers x tels que x2 + x + 4 soient divisibles par 3 et par 5.
    Rép :
    cela revient à résoudre le système x2 + x + 1 ≡ 0 [3] ,  x2 + x - 1 ≡ 0 [5]; on cherche d'abord les x vérifiant la 1ère condition : x = 3k + 1; on cherche ensuite les valeurs possibles de k : k = 5u + 2; d'où x = 3(5u + 2) + 1 = 15u + 7, u entier quelconque. On peut aussi faire usage du théorème chinois ci-après si l'on «s'aperçoit» que 7 est solution et que le système équivaut à  x2 + x + 4 ≡ 0 [3]  ,  x2 + x + 4 ≡ 0 [5].

  4. Bac C &974 : Déterminer les entiers naturels n tels que 52n + 5n soit divisible par 13.
    Rép : clic...

  5. Bac 2006, Ter SpéMath : déterminer les solutions du système nZ, n ≡ 13 [19] , n ≡ 6 [12].
    Rép :
    clic...

  6. Étudier des variantes de l'exercice 5 comme      a) nZ, n ≡ 5 [9] , n ≡ 6 [12]              b) nZ, n ≡ 5 [9] , n ≡ 8 [12].
    Rép : a) impossible.   b) n = 36k - 4

  7. Critère de Lucas-Lehmer et devoir niveau licence.

  8. Polynômes P(x) fournissant des nombres premiers pour des valeurs consécutives de x et limitation de ce type d'images (Euler).

Critères de divisibilité : Classes résiduelles modulo n :  Bézout :
Un théorème fondamental dit théorème de Gauss :

Si l'entier d divise un produit ab d'entiers et si a et d sont premiers entre eux, alors d divise b

Avec la notation a | b pour signifier « a divise b » :

d | ab  et pgcd(a,d) = 1, alors d | b

Preuve : si a et d sont premiers entre eux, il existe des entiers u et v tels que au + dv = 1 (théorème de Bézout). Multiplions par b les deux membres de l'égalité : aub + dvb = b. Puisque d divise le produit aub (puisqu'il divise ab) et d divise évidemment dvb, alors d divise b.

En conséquence de ce théorème, on a ce résultat bien naturel... :

     Si p est premier et divise le produit ab, alors d divise a ou d divise b 
     
(le ou n'étant pas exclusif)

Preuve : si p ne divise pas a, p étant premier il n'a comme diviseur commun avec a que 1. Donc a et p sont premiers entre eux. Et on applique le théorème de Gauss.


a) Etablir (ou admettre car c'est très évident...) que si p et q sont premiers entre eux, il en est de même de p et q3
b) Prouver que si a/b, non entier et irréductible, est solution de l'équation (e) :  3x3 - 2x2 + 6x - 4 = 0 alors a divise 4 et b divise3. En déduire que la seule solution rationnelle de (e) est 2/3.

Zéro rationnel d'un polynôme à coefficients entiers :   

Considérons le polynôme :

P(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a2x2 + a1x + ao

dont les coefficients sont tous entiers. Si x = p/q est un zéro rationnel non entier sous sa forme irréductible, en remplaçant dans P(x), on se ramène à :

p(anpn-1 + an-1pn-2q + an-2pn-3q2 + ... + a2pqn-2 + a1qn-1) = - aoqn

p divise donc aoqn. En application du théorème de Gauss, p étant premier avec q, p divise ao. De la même façon, q divise an. Si ao et an sont relativement petits dans Z, on pourra déterminer une solution rationnelle éventuelle par épuisement des cas. 

Le théorème chinois :

Le théorème suivant, souvent appelé théorème chinois ou lemme chinois apparaît chez Qin Jiushao (1202-1261) dans son Traité de Mathématiques en Neuf Chapitres, mais il est sans doute antérieur encore. En notations modernes, on peut ainsi l'énoncer  :

Soit n1 et n2 deux entiers naturels, x un entier relatif tel que : x ≡ r1  [n1] et x ≡ r2  [n2],  alors :

Preuve : lorsque n1 et n2 sont premiers entre eux, il existe, selon un célèbre théorème de Bézout, un couple (u,v) d'entiers relatifs tels que n1u + n2v = 1. On vérifiera facilement que xo = n1ur2 + n2vr1.

Par exemple : considérons le système x ≡ 2  [3] et x ≡ 3  [5]. 3 et 5 sont premiers entre eux : on a 23 - 15 = 1. Donc x = 233 - 152 = 8 est solution. Toutes les autres sont données par x ≡ 8 [15].

Résidu quadratique, loi de réciprocité quadratique de Gauss-Legendre :

p et q désignant des entiers impairs premiers, dont l'un (au moins) est de la forme 4n + 1 :
si x2 est congru à p modulo q alors x2 est
congru à q modulo p.

Énoncée par Legendre (1830), démontrée par Gauss, cette loi est d'une grande importance en théorie additive des nombres. Rappelons, avec des notations modernes, que dans l'anneau Z/nZ des classes résiduelles modulo n, un résidu quadratique r est un élément congru à un carré modulo n : il existe un entier x tel que r ≡ x2  [n]

La loi de réciprocité quadratique peut s'exprimer ainsi :

 Si x est un résidu quadratique modulo y, alors y est un résidu quadratique modulo x.

 Pour en savoir (beaucoup) plus :

1. Quelles sont les entiers relatifs qui, divisés par 5 et par 3 donnent respectivement les restes 1 et 2 ?    
2. Quels sont les entiers n tels que 4n2 + 1 soient multiples de 5 ?

Des résultats obtenus au moyen des congruences et des résidus quadratiques :
  • Tout nombre premier de la forme 4n + 1 se décompose de façon unique en somme de deux carrés (résultat connu depuis Euler, 1754) :
     Entiers de Gauss :       Goldbach , Lagrange
  • Tout nombre parfait pair se termine par 6 ou 8.
Plus difficile, le résultat suivant, prouvé par Gauss avait été vainement étudié par Legendre qui l'avait conjecturé :

Programmation du théorème des 3 carrés :  

La distribution des nombres premiers, théorème des nombres premiers, le logarithme intégral :

On sait depuis Euclide que l'ensemble des nombres premiers est infini et les mathématiciens se demandaient depuis quelle était leur répartition dans l'ensemble des entiers naturels pour n "grand", nN. On parle de distribution asymptotique des nombres premiers.

Des calculs "à la main" montrent leur raréfaction : si π(n) désigne le nombre de nombres premiers inférieurs à l'entier naturel, une conjecture présumée par Euler, dite aujourd'hui conjecture d'Euler-Gauss ou de Gauss-Legendre, fut étudiée et validée par Gauss en 1792 et par Legendre en 1798. Elle peut ainsi s'énoncer :

π(n) désignant le nombre de nombres premiers inférieurs à n, on a π(n) ~ n/ln n
ln désignant le logarithme népérien
.

le signe ~ signifiant une équivalence pour n "grand".

En d'autres termes, (εn) désignant une suite numérique de limite nulle, on a π(n) =  (1 + εn)n/ln n. Ou encore, comme l'avait prédit Tchebychev en 1848 :

La conjecture eut des formulations beaucoup plus subtiles et précises et constitue ce que l'on appelle généralement aujourd'hui le théorème des nombres premiers car elle fut prouvée un siècle plus tard (1896)par Hadamard et La Vallée-Poussin.

En 1948, Selberg en donnait une seconde formulation. Mais avant cela, en recherchant manuellement le nombre de nombres premiers par tranches de 1000 entiers consécutifs, Gauss estime leur densité à 1/ln(n) et en introduisant la fonction logarithme intégrale notée li (en 1849, il a alors 72 ans) :

Il montre que l'on peut écrire, (O désigne la notation de Landau, certes anachronique ici) :

Nombreux sont les mathématiciens, comme ceux désignés ci-dessous, qui apportèrent leur contribution à une nouvelle preuve où à un affinement de cet important résultat :

  Tchebychev , Dirichlet , Hardy , Littlewood , Ramanujan , Brun , Landau , Erdös , Selberg , Tao

Les méthodes d'investigation purement arithmétiques (science du nombre, du grec arithmos = nombre) en théorie des nombres ne suffisent plus aujourd'hui au regard de la complexité des sujets étudiés. On l'a vu en particulier avec la preuve par Wiles, en 1995, du fameux théorème de Fermat. Comme on le voit ci-dessus, l'entrée de l'analyse dans l'arithmétique est particulièrement spectaculaire. On la retrouve également dans les méthodes d'approximation diophantienne pour la résolution d'équations en nombres entiers. On considère que Dirichlet, qui succéda à Gauss à Göttingen, est le fondateur de cette branche moderne et féconde de la théorie des nombres.

Pour les mathématiciens grecs, l'arithmétique fut l'étude des entiers et des rationnels (fractions) en rapport avec la géométrie (voyez, par exemple, Nicomaque).

Aujourd'hui, avec l'aide du calcul différentiel et intégral, des séries, des fonctions analytiques (développables en série), de l'analyse complexe et harmonique, on parle de théorie analytique des nombres. Le lecteur pourra comparer les différentes éditions du Que-sais-je n°571 Les nombres premiers rédigés par Émile Borel en 1953 , Jean Itard en 1969 et Gérald Tenenbaum & Michel Mendes-France en 1997 où l'immixtion de l'analyse est respectivement quasiment nulle, peu présente, omniprésente...


vidéo YouTube : Le Monde est-il mathématiques ? Les nombres premiers

Cryptographie :

Les nombres premiers sont encore très étudiés et on est loin d'avoir percé tous leurs secrets (voyez, par exemple, Goldbach et Tao dans le cadre de la théorie additive des nombres). Ils ont trouvé un nouveau champ d'application dans la cryptographie, on parle même aujourd'hui de cryptologie. Autrefois utilisée par les seuls militaires ou gouvernements, cette "science" nouvelle voit son application dans les problèmes de confidentialité liés aux télécommunications et à l'Internet en particulier.

Cryptographie et cryptogramme :

 Pour en savoir plus :


© Serge Mehl - www.chronomath.com