121 Nombres premiers. Applications.

Nombres premiers. Applications.

algebra

Généralités

Nombres premiers et premiers entre eux

Définition 1. Soient . On dit que divise (ou que est un multiple de ), et on note s’il existe tel que . Dans le cas contraire, on note .

Théorème 2 (Division euclidienne dans ).

Définition 3. Soient . Par principalité de , il existe un unique tel que Ainsi défini, s’appelle le pgcd de et on note .

Remarque 4. Dans la définition précédente, est le plus entier naturel divisant tous les .

Définition 5. Soient . Lorsque , on dit que sont premiers entre eux dans leur ensemble. Lorsque dès que , on dit que sont premiers entre eux deux à deux.

Théorème 6 (Bézout). Soient .

Théorème 7 (Gauss). Soient .

Définition 8. On dit qu’un entier naturel est premier s’il est supérieur ou égal à et si ses seuls diviseurs positifs sont et .

Exemple 9. Les nombres de Fermat sont premiers pour , mais pas pour .

Théorème 10 (Euclide). L’ensemble des nombres premiers est infini.

Théorème 11 (Fondamental de l’arithmétique). Tout entier naturel se décompose de manière unique sous la forme : où les sont des nombres premiers distincts et où les sont des entiers naturels non nuls.

Proposition 12.

  1. Si et , alors .

  2. Soient et . Alors .

Théorème 13 (Fermat). Soient et . Alors :

  1. .

  2. .

Fonctions arithmétiques

Définition 14. On définit :

  • L’indicatrice d’Euler est la fonction qui à un entier , associe le nombre d’entiers compris entre et qui sont premiers avec .

  • La fonction de Möbius, notée , par

Proposition 15.

  1. premiers entre eux, .

  2. Pour tout entier relatif premier avec , .

  3. Pour tout entier naturel , .

Théorème 16 (Formule d’inversion de Möbius). Soient et des fonctions de dans telles que . Alors,

Corollaire 17.

Répartition des nombres premiers

Définition 18. L’ensemble des générateurs de , noté , est formé des racines primitives -ièmes de l’unité.

Proposition 19.

  1. .

  2. , où désigne l’indicatrice d’Euler.

Définition 20. On appelle -ième polynôme cyclotomique le polynôme

Théorème 21.

  1. .

  2. .

  3. est irréductible sur .

Corollaire 22. Le polynôme minimal sur de tout élément de est . En particulier,

Théorème 23 (Dirichlet faible). Pour tout entier , il existe une infinité de nombres premiers congrus à modulo .

Remarque 24. La version forte de ce théorème est que, pour tout entiers naturels , non nuls, il existe une infinité de nombres premiers de la forme , .

Théorème 25 (des nombres premiers). Si , on note le nombre de nombres premiers inférieurs à . Alors,

Théorie des corps

Corps finis

Proposition 26. Les conditions suivantes sont équivalentes :

  1. est un nombre premier.

  2. est un anneau intègre.

  3. est un corps.

Notation 27. On note .

Définition 28. Soit un anneau. L’application On note l’unique tel que : c’est la caractéristique de .

Proposition 29.

  1. Soit un anneau intègre. Alors, avec premier.

  2. Soit un anneau fini. Alors, et .

  3. Un anneau et un quelconque de ses sous-anneaux ont la même caractéristique.

Remarque 30.

  • Le Point 0 est en particulier vrai pour un corps.

  • Si , est infini.

Proposition 31. Soit un corps fini.

  1. est un nombre premier .

  2. Le sous-corps premier de est isomorphe à .

  3. pour .

Proposition 32. Soit un corps de caractéristique . L’application est un morphisme de corps.

  1. Si est fini, c’est un automorphisme.

  2. Si , c’est l’identité.

Théorème 33. Soient et . On pose . Alors :

  1. Il existe un corps à éléments : c’est le corps de décomposition de sur .

  2. est unique à isomorphisme près : on le note .

Corollaire 34 (Théorème de Wilson). Soit un entier. Alors,

Théorème 35. est cyclique, isomorphe à .

Remarque 36. En fait, tout sous-groupe fini du groupe multiplicatif d’un corps commutatif est cyclique.

Théorème 37 (Wedderburn). Tout corps fini est commutatif.

Carrés dans les corps finis

Soit avec premier et .

Proposition 38. On note et . Alors est un sous-groupe de .

Proposition 39.

  1. Si , , donc .

  2. Si , alors :

    • est le noyau de l’endomorphisme de défini par .

    • est un sous-groupe d’indice de .

    • et .

    • .

Notation 40. Soit . On note le symbole de Legendre de modulo . On a ainsi avec si et seulement si .

Application 41 (Frobenius-Zolotarev). Soient un nombre premier et un espace vectoriel sur de dimension finie. est vu comme une permutation des éléments de .

Réduction modulo

Le résultat suivant justifie que l’on s’intéresse aux polynômes irréductibles en théorie des corps.

Théorème 42. Soit un polynôme irréductible sur un corps .

  • Il existe un corps de rupture de .

  • Si et sont deux corps de rupture de , alors il existe un unique -isomorphisme tel que .

  • est un corps de rupture de .

Lemme 43 (Gauss).

  1. Le produit de deux polynômes primitifs est primitif (ie. dont le PGCD des coefficients est égal à ).

  2. , (où est le contenu du polynôme ).

Théorème 44 (Critère d’Eisenstein). Soit de degré . On suppose qu’il existe premier tel que :

  1. , .

  2. .

  3. .

Alors est irréductible dans .

Application 45. Soit . Il existe des polynômes irréductibles de degré sur .

Théorème 46 (Critère d’irréductibilité modulo ). Soit de degré . Soit un premier. On suppose .

Si est irréductible dans , alors est irréductible dans .

Exemple 47. Le polynôme est irréductible dans .

Autres applications en algèbre

Entiers sommes de deux carrés

Notation 48. On note et l’ensemble des entiers qui sont somme de deux carrés.

Remarque 49. .

Théorème 50 (Deux carrés de Fermat). Soit . Alors si et seulement si est pair pour tout premier tel que (où désigne la valuation -adique de ).

En théorie des groupes

Soit un groupe.

Définition 51. On dit que est un -groupe s’il est d’ordre une puissance d’un nombre premier .

Proposition 52. Soit un nombre premier. Si est un -groupe opérant sur un ensemble , alors, désigne l’ensemble des points fixes de sous l’action de .

Corollaire 53. On note les classes de conjugaison de . Alors,

Corollaire 54. Soit un nombre premier. Le centre d’un -groupe non trivial est non trivial.

Corollaire 55. Soit un nombre premier. Un groupe d’ordre est toujours abélien.

Application 56 (Théorème de Cauchy). On suppose non trivial et fini. Soit un premier divisant l’ordre de . Alors il existe un élément d’ordre dans .

RSA

Définition 57. Afin de chiffrer un message (tout entier découpé en séquence d’entiers de taille bornée) en utilisant RSA, on doit a besoin de deux clés :

  • Une clé privée, qui est un couple de nombres premiers .

  • La clé publique correspondante, qui est le couple et est l’inverse de modulo désigne un nombre premier à .

Nous conserverons ces notations pour la suite.

Théorème 58 (Chiffrement RSA). Soit un message où pour tout , .

  1. Possédant la clé publique, on peut chiffrer ce message en un message :

  2. Possédant la clé privée, on peut déchiffrer le message pour reconstituer :

Remarque 59.

  • L’intérêt vient pour des premiers et très grands : il devient alors très compliqué de factoriser et d’obtenir la clé privée.

  • Les inverses peuvent se calculer à l’aide de l’algorithme de Bézout.