L305, exercices illustrant emploi nb premiers
L'intitulé de la leçon 305 Exercices illustrant l'emploi des nombres premiers
ce qui signifie implicitement qu'il faut parler des applications des nombres premiers.
Il y a bien évidemment un exercice sur le codage RSA mais après ?
Par exemple le théorème des restes chinois est hors sujet puisqu'il utilise des nombres premiers entre eux
Y a-t-il des suggestions ?
Merci d'avance
ce qui signifie implicitement qu'il faut parler des applications des nombres premiers.
Il y a bien évidemment un exercice sur le codage RSA mais après ?
Par exemple le théorème des restes chinois est hors sujet puisqu'il utilise des nombres premiers entre eux
Y a-t-il des suggestions ?
Merci d'avance
Mots clés:
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pardon pour cette piètre consolation.
Par exemple, le théorème de Erdös-Ginzburg-Ziv : parmi $2n-1$ entiers, on peut en choisir $n$ dont la somme est divisible par $n$.
On note que si la proposition est vraie pour deux entiers $a$ et $b$, elle est aussi vraie pour $ab$. On peut donc se contenter de la démontrer pour $n$ premier.
(c'est démontré dans pas mal de bouquins comme corollaire du théorème de Cauchy-Davenport et les deux réunis font un développement pour l'oral).
https://fr.wikipedia.org/wiki/Théorème_de_Wilson
Variations autour du théorème de Wilson:
https://www.idpoisson.fr/beck/wp-content/uploads/sites/16/2018/06/cplt-wilson.pdf
Loi de réciprocité quadratique:
https://www.math.u-psud.fr/~perrin/TER/reciprocite.pdf
Qui sert à caractériser, par exemple, quels sont les nombres premiers qui sont somme de deux carrés entiers, quels sont les nombres premiers qui sont de la forme $x^2+5y^2$ etc.
La fonction d'Euler est définie sur $\mathbb{N}$ privé de $0$.
Je trouve cette épreuve sur dossier difficile car il est facile de tomber dans le hors-sujet, même de bonne foi.
-- Schnoebelen, Philippe
Et c'est vrai plus generallement de presque tous les calculs d'objets a coefficients entiers (ou rationnels), mais c'est souvent plus complique a mettre en oeuvre que le calcul du determinant (surtout au niveau agreg interne), par exemple le PGCD de polynomes a coefficients rationnels. Le theoreme des restes chinois en association avec du calcul dans des corps finis premiers est incontournable en calcul formel, c'est probablement l'outil le plus utilise. Ce serait quand meme tres dommage de passer a cote dans une lecon ayant l'intitule de la 305.
https://fr.wikipedia.org/wiki/Critère_d'Eisenstein
Ton exemple est bon mais je soulignais la difficulté de trouver des exercices où les nombres premiers ne sont pas juste un cache-misère.
Par exemple un exercice où on démontre qu’une équation diophantienne n’a pas de solution en réduisant modulo un truc… pourquoi modulo un premier (disons 7) alors que modulo 4, ça marche aussi ?
-- Schnoebelen, Philippe
De toute façon, il faudra bien justifier l’intérêt de l’usage de nombres premiers dans un tel exercice parce que l’argument « ben ça marche » risque d’être reçu froidement ou par une question où justement il attend les hypothèses précises du théorème des restes chinois. Je pense qu’il est facile de coincer un candidat.
-- Schnoebelen, Philippe
Par ailleurs, tout nombre entier est produit de puissances d'un nombre premier donc cela justifie-t-il des exercices avec la fonction d'Euler, le théorème des restes chinois etc pour cet item?
PS:
Est-ce que c'est une bonne idée de donner l'impression à un jury d'un tel concours qu'on confond nombres premiers et nombres premiers entre eux?
https://fr.wikipedia.org/wiki/Chiffre_de_Hill
Mais là aussi il n'y a pas besoin de convoquer absolument un nombre premier même si cela facilite sans doute les choses.
On considère une matrice carrée d'ordre $r$ inversible* dans $\mathbb{Z}/n\mathbb{Z}$ avec $n\geq 26$
L'alphabet ordinaire $A,B,C,........,Z$ est converti en $0,1,2,....,25$ et on peut rajouter des symboles si $n>26$
On saucissonne un message en tranches de $r$ symboles et on applique la matrice de chiffrement à ces tranches de vecteurs à $r$ composantes. Le résultat obtenu est le message chiffré.
*: pour qu'elle soit inversible il faut et il suffit, me semble-t-il, que le déterminant soit premier avec $n$.
Quand $n$ est premier il faut que le déterminant ne soit pas divisible par $n$. Cela rend plus facile la création d'une matrice de chiffrement me semble-t-il aussi.
-- Schnoebelen, Philippe
Après, chacun fait comme il l’entend et je ne suis pas membre de jury de concours.
C’est tout-à-fait ça, Dom. Et si on a peu préparé cette leçon, je crains que les question du jury soient cruelles.
-- Schnoebelen, Philippe
Je persiste : si la résolution de l’exercice est présentée avec un modulo premier un peu grand (même 17) alors que ça se fait modulo 4 (mais pas modulo 2), le candidat va avoir du mal à se dépatouiller des questions du jury.
Je pense surtout qu’il faut bien réfléchir aux exercices proposés et voir où est l’intérêt de l’usage des nombres premiers parce que si on se contente d’un « ben ça marche » alors qu’on peut tout aussi bien faire sans…
-- Schnoebelen, Philippe
En calcul sur machine, on utilise en general des nombres premiers d'un peu moins de 32 bits pour pouvoir faire efficacement toutes les operations arithmetiques. On est parfois oblige de travailler sur des structures qui ne sont pas des corps, mais si on peut l'eviter on l'evite!
Un autre exemple ou utiliser un nombre premier est essentiel: tester si un polynome donne n'a pas de racine multiple (par exemple pour en chercher des racines approchees par la methode de Newton). On tire au hasard un polynome unitaire de degre disons 4, on calcule le pgcd de p et p' modulo deux ou trois nombres premiers par Euclide, des qu'on trouve un polynome constant on a gagne. Le meme calcul sur les rationnels est bien plus fastidieux.
Si l’exercice n’est pas assez préparé, le candidat risque de se retrouver dans ce genre de situation déstabilisante.
-- Schnoebelen, Philippe
Nicolas met en garde à un exemple mal choisi.
Je tente un exemple métaphorique :
Utiliser le théorème des fonctions implicites pour démontrer que l’identité dans $R$ est bijective sur un intervalle peut être une source de pépins...
Mais ce n’est qu’une mise en garde, enfin, c’est ce que je comprends.
Tu trouveras dans ce livre des exemples :
1) Une "réciproque"* du petit théorème de Fermat. Résultat du à Lucas sauf erreur (je ne crois pas que ce bouquin source ce résultat)
2)Il y a aussi la divergence de la série des inverses des nombres premiers.**
3)Un exercice sur les nombres de Fermat (sous prétexte que $641$,nombre premier, divise $F_5$ j'imagine, parce que autrement cet exercice ne me semble pas très pertinent ici: il aurait mieux valu parler des nombres de Mersenne à mon humble avis)
4)Un exercice sur le fait que le groupe multiplicatif de $\mathbb{Z}/p\mathbb{Z}$ est cyclique.
5)Un exercice sur un résultat du à Frobenius je pense, Soit $G$ un groupe d'ordre $N$ et $p$ premier divise $N$
Il y a une propriété sur le nombre de solutions de l'équation $x^p=1$ dans $G$.
6)Un exercice sur le crypto-système RSA (le bouquin ne source pas la vraie origine de ce résultat, je crois qu'il y a un renvoi à un autre bouquin comme seule source me semble-t-il)
*: ce n'est pas une réciproque à proprement parler.
**: Je me demande si cet exercice n'est pas hors sujet: peut-être qu'il vaudrait mieux remplacer par la formule d'Euler: l'expression de $\zeta(s)$, avec $s>1$ comme produit infini. J'imagine que la solution à l'exercice proposé utilise cette formule.
PS:
J'ai peut-être été injuste avec les nombres de Fermat: Ceux qui sont premiers ont une forme bien particulière $2^{2^n}+1$.
Montrer des inégalités de type Tchebychev, qui permettent de minorer/majorer $\pi(x)$ le nombre de nombres premiers inférieurs ou égaux à $x$.
Je ne sais plus dans quel concours il y avait une version affaiblie de ce résultat qui servait de base à un problème (ou le problème tournait autour de ce thème je ne sais plus)
Agrégation mathématique, épreuve orale , 68 thèmes pour se préparer efficacement, Ivan Nourdin, Dunod.
Mais un exercice qui permet de faire une démonstration c'est toléré, et même apprécié pour les démonstrations qui mettent en avant des raisonnements ou des résultats pratiques pour la résolution d'exercices qui entre dans le thème.
Un exemple concret, même s'il est peut être d'un niveau un peu juste pour l'agreg interne, c'est de démontrer la formule qui donne le nombre de diviseurs d'un nombre entier en fonction de sa décomposition en facteurs premiers.
Ça donne une méthode pour établir la liste des diviseurs pour un nombre entier.
Pour moi le critère d'Eisenstein est sympa dans cette leçon, tant pour sa démonstration que pour son utilisation qui rentrent dans le thème.
Alacool.