Leçon 121 : Nombres premiers. Applications.

(2019) 121

Dernier rapport du Jury :

(2017 : 121 - Nombres premiers. Applications.) Le sujet de cette leçon est très vaste. Aussi les choix devront être clairement motivés. La réduction modulo p n’est pas hors-sujet et constitue un outil puissant pour résoudre des problèmes arithmétiques simples. La répartition des nombres premiers est un résultat historique important qu’il faudrait citer. Sa démonstration n’est bien sûr pas exigible au niveau de l’agrégation. Quelques résultats sur les corps finis et leur géométrie sont les bienvenus, ainsi que des applications en cryptographie.

(2016 : 121 - Nombres premiers. Applications.) Le sujet de cette leçon est très vaste. Aussi les choix devront être clairement motivés. La réduction modulo p n’est pas hors-sujet et constitue un outil puissant pour résoudre des problèmes arithmétiques simples. La répartition des nombres premiers est un résultat historique important qu’il faudrait citer. Sa démonstration n’est bien sûr pas exigible au niveau de l’agrégation. Quelques résultats sur les corps finis et leur géométrie sont les bienvenus, ainsi que des applications en cryptographie.
(2015 : 121 - Nombres premiers. Applications.) Il s'agit d'une leçon pouvant être abordée à divers niveaux. Il y a tant à dire sur la question que le candidat devra fatalement faire des choix. Attention toutefois à celui des développements, ils doivent être pertinents ; l'apparition d'un nombre premier n'est pas suffisant ! La réduction modulo p n'est pas hors-sujet et constitue un outil puissant pour résoudre des problèmes arithmétiques simples. La répartition des nombres premiers est un résultat historique important, qu'il faudrait citer. Sa démonstration n'est bien sûr pas exigible au niveau de l'agrégation. Quelques résultats sur les corps finis et leur géométrie sont les bienvenus, ainsi que des applications en cryptographie.
(2014 : 121 - Nombres premiers. Applications.) Il s'agit d'une leçon pouvant être abordée à divers niveaux. Attention au choix des développements, ils doivent être pertinents (l'apparition d'un nombre premier n'est pas suffisant !). La réduction modulo $p$ n'est pas hors-sujet et constitue un outil puissant pour résoudre des problèmes arithmétiques simples. La répartition des nombres premiers est un résultat historique important, qu'il faudrait citer. Sa démonstration n'est bien-sûr pas exigible au niveau de l'Agrégation. Quelques résultats sur la géométrie des corps finis sont les bienvenus.

Développements :

Plans/remarques :

2019 : Leçon 121 - Nombres premiers. Applications.


2018 : Leçon 121 - Nombres premiers. Applications.


2017 : Leçon 121 - Nombres premiers. Applications.


2016 : Leçon 121 - Nombres premiers. Applications.


2015 : Leçon 121 - Nombres premiers. Applications.


Retours d'oraux :

2019 : Leçon 121 - Nombres premiers. Applications.

  • Leçon choisie :

    121 : Nombres premiers. Applications.

  • Autre leçon :

    107 : Représentations et caractères d’un groupe fini sur un C-espace vectoriel. Exemples.

  • Développement choisi : (par le jury)

    Loi de réciprocité quadratique (via les formes quadratiques)

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    J'ai fait des erreurs de notation dans mon développement et dans mon plan, notamment un problème de définition du symbole de Legendre ; on a passé un certain temps - 10/15 minutes je dirais - à remettre tout ça en ordre. POur ce qui est des questions, je me souviens de celles-ci :
    - Expliquer rapidement la démonstration de la classification des formes quadratiques sur un corps fini
    - 15 est-il un carré modulo 37 ? (et montrer que le symbole de Legendre est multiplicatif)
    - Donner une application du théorème de Cauchy sur les groupes : je n'en avais pas, j'ai fais quelques remarques sur le résultat (notamment dit que c'était une réciproque partielle du théorème de Legendre) ; on m'a demandé d'expliquer pourquoi dans un groupe abélien fini le produit de 2 éléments dont les ordres sont premiers entre eux est un élément d'ordre le produit des ordres, avec un contre-exemple dans le cas non abélien
    - A la fin : s'inspirer de la démonstration du théorème des 2 carrés pour trouver les nombres premiers irréductibles dans Z[sqrt(d)] ; après quelques remarques et indications, le temps était écoulé.

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Jury globalement souriant, plutôt vers la fin qu'au début je dirais, mais jamais désagréable.

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    C'était le 1er jour de canicule, j'ai dû aller me mettre de l'eau sur le visage plusieurs fois pour ne pas avoir trop chaud ; il faut bien penser à boire et à manger pendant la préparation (on oublie facilement dans ces circonstances) pour éviter de se sentir faible devant le jury

  • Note obtenue :

    17.75

  • Leçon choisie :

    121 : Nombres premiers. Applications.

  • Autre leçon :

    107 : Représentations et caractères d’un groupe fini sur un C-espace vectoriel. Exemples.

  • Développement choisi : (par le jury)

    Critère d'Eisenstein + application à l'irréductibilité de $\Phi_p$ [no pdf]

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    Niveau développement, le jury avait le choix entre : "Le critère d'Eisenstein et l'application à l'irréductibilité de $\Phi_p$" ou "Le théorème des deux carrés de Fermat (par les entiers de Gauss)"...

    J : Sur le développement, pourquoi $p$ divise les coefficient $q_i$ et $r_i$ ? Par exemple que se passerait-il si $p=8$ ?
    R du candidat : En particulier comme $\mathbb{Z}/p\mathbb{Z}$ est un corps pour $p$ premier, $\mathbb{Z}/p\mathbb{Z}[X]$ est un anneau principal donc factoriel et il y a alors l'unicité de la décomposition en irréductibles. Pour $p=8$, j'exhibe un contre-exemple simple, ce qui montre l'importance de $p$ nombre premier. (Le jury ne semble pas convaincu).

    J : Rappeler pourquoi $p$ divise $\binom{p}{k}$ pour $k\in [1,p-1]$ ? (Par rapport à l'irréductibilité de $\Phi_p$ toujours dans l'application de mon développement).
    R du candidat : J'écris l'égalité du coefficient binomial à sa forme fractionnaire et fait passer le dénominateur de l'autre côté afin d'appliquer le lemme de Gauss élémentaire sur la divisibilité. Ils voulaient plus de précision, j'ai donc utilisé le théorème de Wilson (c'était dans mon plan) en précisant qu'on peut le démontrer par Bézout, pour justifier totalement la divisibilité initiale. (Le jury dit ok).

    J : Sur le plan pédagogique pourquoi avoir fait une sous-partie "nombres premiers entre eux" ?
    R du candidat : Je trouve que le titre "nombres premiers" est pas suffisamment précis, donc je trouve que c'est plutôt légitime d'en parler un peu. D'ailleurs je l'ai aussi fait, car si on prend le cas de deux nombres premiers, ils sont forcément premiers entre eux, et cela permet d'obtenir d'autre propriétés intéressantes sur l'arithmétique des entiers telles que le lemme chinois avec les problèmes de congruences ou encore les équations diophantiennes de degré 1. (Le jury dit ok).

    J : Comment savoir si un nombre est premier ?
    R du candidat : Je précise dans mon plan, qu'en partie 4, j'ai parlé de trois tests importants de manière logique et progressive dont un probabiliste (Fermat, Euler et Solovay-Strassen) mais qu'il existe des tests plus basiques comme le crible d'Eratosthène ou encore celui de la méthode des diviseurs premiers jusqu'à la partie entière de la racine du nombre. Exemple sur 113 où j'en profite pour rappeler les règles de divisions par $2$, $3$ et $5$ et aussi comment la division euclidienne peut être utile. (Le jury dit ok).

    J : D'ailleurs, pour une équation diophantienne de degré $1$, y a-t-il unicité du couple de solutions ?
    R du candidat : Non d'après le théorème de Bézout, il existe une infinité de couple d'entiers qui vérifie par exemple l'équation $ax+by=1$. On essaye par exemple sur $a=5$ et $b=7$ où on trouve des solutions particulières à la main (petits nombres) et on applique la méthode habituelle pour avoir la forme générale des couples de solutions. Au lieu de $1$ on peut prendre $d$ entier tel que $pgcd(a,b)$ divise $d$. (Le jury dit ok).

    J : Mais sinon y a-t-il des méthodes algorithmiques pour trouver de tels couples d'entiers ?
    R du candidat : On peut commencer par utiliser l'algorithme une division euclidienne jusqu'au dernier reste non nul et on fait ce qu'on appelle une remontée de Bézout. Mais algorithmiquement c'est lourd. Sinon de manière plus efficace on peut utiliser l'algorithme étendu d'Euclide. (Le jury dit ok et ne semble pas en vouloir plus).

    J : A quel autre domaine des mathématiques vous fait penser une équation de la sorte ?
    R du candidat : On peut penser notamment au domaine de l'algèbre linéaire notamment avec le cas des systèmes affines (ici). On reprend l'exemple de $a=5$ et $b=7$ et ils me demandent le noyau "du système". On trouve bien une droite linéaire. (Le jury dit ok).

    J : Ok, prenons l'équation $x^2+y^2=7z^2$. Quelles sont les solutions entières ?
    R du candidat : Le premier réflexe que j'ai c'est de passer modulo $7$ et c'est la bonne idée. Ils me précisent que l'on fait l'hypothèse qu'un des deux est inversible modulo $7$. Donc j'arrive une contradiction avec une propriété sur les carrés modulo $p=7$ (le fameux critère $p\equiv 1 \pmod 4$). Et je précise aussi que puisque $7$ est un nombre premier, $\mathbb{Z}/7\mathbb{Z}$ est un corps donc un des deux $x$ ou $y$ est nécessairement divisible par $7$. Ils me demandent ensuite s'il n'y a pas une solution qui marche directement et je précise en effet que la triviale convient. On l'élimine donc et pour conclure l'exercice, j'ai du mettre en place comme je le précise au jury la méthode de "descente infinie" afin de terminer et s'apercevoir que seul $(0,0,0)$ marche. (Le jury dit ok).

    J : Expliquez RSA et sa sécurité ?
    R du candidat : J'explique plus en détails l'énoncé du plan car c'était peut-être mal rédigé et du coup c'est plus clair dans leur tête. Ensuite, je précise par rapport à la sécurité de RSA, que si un attaquant souhaitait intercepté le message (sans clé privée bien sûr) il devrait extraire une racine $e$-ième modulo $p$. C'est un problème type "log discret" qui est généralement "difficile". (Le jury dit ok).

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Ils étaient corrects et bienveillants. Ils m'ont donné des petites indications quand je mettais un peu de temps à répondre mais ils laissaient le temps de s'exprimer. Déçu qu'ils n'aient pas poser de questions sur la partie "théorie des anneaux" où les éléments premiers ne sont pas toujours ceux que l'on croit. Dommage car c'est une partie intéressante mais bon... Les trois jurys ont participé a la discussion. Au final, je pensais m'être débrouillé et avoir fait un oral correct (je pensais avoir au moins la moyenne par exemple) mais au vue de la note finale, on peut se fier à rien et encore moins à leur attitude (peut-être qu'ils n'ont pas accroché à mon approche de cette leçon, je ne sais pas). C'est la vie :'( ...

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Il faut compter environ 2h40 pour composer (chercher les livres dans les malles ou dans son sac et faire attention au moment des photocopies). J'avais préparé sérieusement cette leçon pendant l'année en classe (de base j'étais allé plus loin, notamment dans les tests de primalités et les notions de factorisation de grands nombre ainsi que dans le domaine des racines modulo $p$) mais le jour-j, avec le stress, on en sait un peu moins que d'habitude et donc j'ai mis les résultats où j'étais sûr. Mais bon je ne sais pas si ça a changé grand chose au final. Donc je recommanderais, de bien s'entraîner au format 3h pendant l'année pour avoir aucune surprise...

    Sinon les surveillants dans les salles et ceux qui mènent à "l'abattoir" sont sympathiques et disponibles !

  • Note obtenue :

    4.25


2017 : Leçon 121 - Nombres premiers. Applications.

  • Leçon choisie :

    121 : Nombres premiers. Applications.

  • Autre leçon :

    162 : Systèmes d'équations linéaires ; opérations élémentaires, aspects algorithmiques et conséquences théoriques.

  • Développement choisi : (par le jury)

    Théorème de Chevalley-Warning

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    Jury attentif pendant le plan et le développement, pas de questions sur le développement.
    Questions :
    - pourquoi est-ce qu'il existe des polynômes irréductibles de tout degré dans $\mathbb{F}_q$ ? (parce que $\mathbb{F}_{q^n}^{\times}$ étant cyclique, $\mathbb{F}_{q^n}$ est une extension monogène de $\mathbb{F}_q$, il suffit de prendre le polynôme minimal d'un générateur)
    - trouver une condition nécessaire pour que $2^n-1$ soit premier (réponse : $n$ premier).
    - si G est un groupe tel que l'action naturelle de $\mathrm{Aut}(G)$ sur $G$ n'a que deux orbites, que peut-on dire de $G$ ? (réponse : $G$ est un p-groupe abélien isomorphe à un certain $(\mathbb{Z}/p\mathbb{Z})^n$. Pour cela, montrer que $Z(G)$ est un sous-groupe caractéristique pour obtenir que $G=Z(G)$, puis constater que tous les éléments non triviaux de $G$ sont de même ordre, qui est donc nécessairement premier et finir en utilisant le théorème de structure des groupes abéliens finis ou en remarquant que $G$ peut être vu comme un $\mathbb{F}_p$-espace vectoriel).
    - quelle est la structure du groupe $(\mathbb{F}_q,+)$ ? (réponse : idem.)

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Un des trois membres du jury posait essentiellement toutes les questions et les autres essayaient d'aider ou posaient de petites questions sur le plan.

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Un peu surpris par l'absence de question sur le plan, mais sinon j'aimais bien cette leçon.

  • Note obtenue :

    19

  • Leçon choisie :

    121 : Nombres premiers. Applications.

  • Autre leçon :

    181 : Barycentres dans un espace affine réel de dimension finie, convexité. Applications.

  • Développement choisi : (par le jury)

    Théorème du point fixe de Kakutani et sous-groupes compacts de GLn(R)

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    1. Pouvez-vous rapidement montrer que les sous-groupes finis de $\textrm{GL}_n(\mathbb{R})$ sont conjugués à des sous-groupes de $O(n)$?
    2. Démontrer le théorème de Gauss-Lucas.
    3 L'intérieur d'un convexe est-il toujours convexe ? Si oui, pourquoi ?
    4. Quels sont les points extrémaux de l'ensemble des matrices bistochastiques ?

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Les trois membres du jury étaient attentifs et intervenaient régulièrement pour me questionner, mais aussi me guider dans la difficulté.

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Aucune surprise.

  • Note obtenue :

    15.75

  • Leçon choisie :

    121 : Nombres premiers. Applications.

  • Autre leçon :

    157 : Endomorphismes trigonalisables. Endomorphismes nilpotents.

  • Développement choisi : (par le jury)

    Théorème de Dirichlet faible

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    Quelques précisions sur le développement ont été demandées.
    Ensuite on m'a donné des exercices en lien avec le théorème de Wilson et son utilisation.

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Le jury était globalement là pour aider et faire avancer la discussion.

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Pas de réponse fournie.

  • Note obtenue :

    Pas de réponse fournie.

  • Leçon choisie :

    121 : Nombres premiers. Applications.

  • Autre leçon :

    103 : Exemples de sous-groupes distingués et de groupes quotients. Applications.

  • Développement choisi : (par le jury)

    Irréductibilité des polyômes cyclotomiques sur Q

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    -Montrer que 561 est de Carmichael sans la caractérisation explicite (Réponse : Regarder les $a^{561}$ mod(3),mod(11),mod(17) + Th chinois)
    -Montrer que la définition du n-ième polynôme cyclotomique dans $\mathbb{C}$ et dans $\mathbb{\F_p}$ (p premier à n) coïncident. (Réponse : Utiliser la relation $\Pi_{d|n} \Phi_d = X^n-1$ )
    -Montrer que pour p premier à n, les facteurs de $\Phi_n$ dans $\mathbb{\F_p}$ sont de degré égal à l'ordre de p dans $(Z/nZ)^x$. (Réponse : Prendre un facteur irréductible, regarder le corps de rupture, et raisonner sur le degré de l'extension car on doit avoir $p^m \equiv 1$ mod(n) )
    -Montrer que si $(Z/nZ)^x$ est cyclique, il existe un p premier générateur de ce groupe. (Réponse : Utiliser le théorème de la progression arithmétique de Dirichlet.)
    -Montrer que si P,Q $\in \mathbb{Z}[X]$ unitaires sont de pdcd $\neq$ 1 dans $\mathbb{C}[X]$, c'est encore le cas dans $\mathbb{Z}[X]$ (Réponse : On a le résultat dans $\mathbb{Q}[X]$ par contrapposée, puis on utilise le Lemme de Gauss et le contenu pour trouver un diviseur dans $\mathbb{Z}[X]$ de P.)
    -Donner un bon algorithme déterministe de primalité (Réponse : Algorithme AKS)
    -Expliquer "méthode de Monte-Carlo" (Réponse : Algorithme utilisant de la génération aléatoire, qui répond en temps fini, qui a toujours raison s'il répond "Non", mais qui a une probabilité d'erreur s'il répond "Oui". Ex : Test de Miller-Rabin pour savoir si n n'est pas premier.)
    -Expliquer le test de Miller-Rabin (Réponse : Utiliser k variables aléatoires de loi uniforme sur $\{1,..,n-1\}$ et tester si les entiers générés sont témoins de Miller-Rabin de n ou non.)
    -Donner la complexité du test de primalité naïf (Réponse : $O( exp(1/2.log_2(n)) )$, donc exponentiel )
    -Expliquer les calculs de chiffrement du RSA + donner la complexité (Réponse : Exponentiation binaire dans Z/nZ, O(log(e)) produits dans Z/nZ. )
    -Est-ce que casser RSA <-> Résoudre le problème de factorisation n=pq ? (Réponse : On ne sait pas)
    -Comment retrouver d avec (p-1)(q-1) et e. (Réponse : Euclide étendu)

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Bienveillant dans le fond.
    L'un des membres a fait toutes les questions concernant l'algorithme RSA et la complexité.
    Sinon, ils m'ont aidé à remettre les idées de mon développement en ordre (j'avais oublié le bon ordre pour les utiliser).

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Plan de rêve, préparation tranquille. Mais j'ai quand même réussi à mélanger l'ordre des idées de mon développement, ce qui m'a attristé car c'était un développement tout simple. (Remarque : En ayant mélangé tous mes arguments, mais en étant capable de me corriger à chaque erreur de logique, j'ai quand même eu 5/6 au développement. La bienveillance était donc de mise.)

  • Note obtenue :

    19