L305, exercices illustrant emploi nb premiers

stephane_idf

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

Dom

Ou alors on sauve l'application des restes chinois en disant qu'en prenant deux nombres premiers distincts, alors ils sont premiers entre eux.

Pardon pour cette piètre consolation.

stephane_idf

Je peux faire la décomposition primaire d'un nombre puis application au calcul du pgcd et ppcm, ça fait un deuxième exo mais il en faut entre 4 et 6

Dom

Quel concours ?

stephane_idf

c'est l'agreg interne leçon 305

Eric

Comme tu le fais remarquer, un résultat utilisant le théorème de décomposition en facteurs premiers répond à ta question.

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).

parisse

Le theoreme des restes chinois est tres utilise en calcul exact, et toujours avec un nombre premier et un produit de nombres premiers, il me semble donc parfaitement dans le sujet. Par exemple pour calculer un determinant de matrice a coefficients entiers en utilisant des determinants modulo un nombre suffisant de nombres premiers.

Fin de partie

Caractérisation des nombres premiers: Théorème de Wilson.
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.

geo

Fonction d'Euler

Fin de partie

Geo:
La fonction d'Euler est définie sur $\mathbb{N}$ privé de $0$.

nicolas.patrois

Le théorème des restes chinois me semble un peu hors-sujet car il nécessite des nombres premiers entre eux, des premiers distincts ça fonctionne mais ça me semble juste pour illustrer l’emploi de nombres premiers.
Je trouve cette épreuve sur dossier difficile car il est facile de tomber dans le hors-sujet, même de bonne foi.

xax

La construction des nombres p-adiques

parisse

@nicolas.patrois: pas du tout d'accord avec vous, l'exemple que je donnais, un exercice sur le calcul du determinant d'une matrice a coefficients entiers par reduction modulo plusieurs nombres premiers et application du theoreme des restes chinois est completement dans le sujet.

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.

Fin de partie

Il y a aussi le critère d'Eisenstein:
https://fr.wikipedia.org/wiki/Critère_d'Eisenstein

nicolas.patrois

parisse a écrit:

pas du tout d'accord avec vous, l'exemple que je donnais, un exercice sur le calcul du déterminant d'une matrice a coefficients entiers par réduction modulo plusieurs nombres premiers et application du théorème des restes chinois est complètement dans le sujet.

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 ?

parisse

Parce que modulo un nombre premier on a plus de structure que modulo un entier quelconque, c'est quand meme plus facile de travailler sur un corps et on risque beaucoup moins de faire des erreurs, par exemple l'equation x^2=3 mod 143 admet 4 solutions alors que c'est une equation de degre 2.

nicolas.patrois

On a peut-être plus de structure (du moins une structure plus facile à utiliser) mais si le jury te tue ton exo avec un modulo 4, tu n’as pas l’air idiot. :-D
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.

Fin de partie

Les puissances de $2$ semblent être de bons candidats à l'occasion pour montrer qu'une équation diophantienne n'a pas de solutions (par réduction modulo $2^k$) me semble-t-il.

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?

Fin de partie

Un autre exemple de chiffrement:

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.

nicolas.patrois

Une autre manière, dans $\Z/29\Z$, est faite dans le sujet d’algèbre de 2007 de l’agrégation externe (chiffrement El-Gamal). Ça ressemble à RSA mais c’est plus original et on peut même y ajouter une pointe de hasard.

Romyna

[size=large]Comment chiffrer avec une courbe ? Par leur entremise...[/size]

parisse

@nicolas.patrois: Mon avis personnel c'est que si un jury declare hors sujet ici l'utilisation des restes chinois pour remonter des calculs faits dans des Z/pZ pour plusieurs p premiers, alors il n'est pas digne d'etre jury.

Dom

Bon, à mon avis, ce qui compte c'est que le candidat sache argumenter pour dire que "le truc" dont il parle est dans le sujet. Que les candidats aient des avis divergents, c'est évident et ce n'est pas grave du tout.

nicolas.patrois

Je n’ai pas écrit ça, j’ai écrit que résoudre un exercice en se gargarisant d’utiliser les nombres premiers alors qu’ils ne sont pas nécessaires risque d’être périlleux.
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.

parisse

Le rapport du jury dit qu'il faut priviligier les methodes de resolution generales aux astuces specifiques (ce que j'appelle des astuces de cow-boy), la reduction modulo un nombre non premier pour resoudre un exercice particulier rentre plutot dans la seconde categorie, alors que la reduction modulo un nombre premier rentre clairement dans la premiere.

nicolas.patrois

Modulo 4, c’est une astuce de cow-boy et pas modulo 17 ? Vraiment ?
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…

parisse

Oui, modulo 4 c'est une astuce de cow-boy, qui marchera peut-etre pour un cas particulier mais echouera generiquement, alors que travailler modulo des nombres premiers c'est une methode generale. En plus je ne vois franchement pas en quoi c'est plus difficile de calculer a la main modulo 3, 5, 7 ou 11 que modulo 4, et au moins il n'y a pas de piege, du genre 2 non nul mais pas inversible.
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.

nicolas.patrois

Ce n’est pas une question de difficulté ou de généralité mais de se préparer à des questions du jury. C’est bien beau de montrer que modulo 2, 3, 5, 7, 11 et 13 on ne trouve rien alors que modulo 17 ça marche si le jury exhibe un modulo 4 qui marche lui aussi.
Si l’exercice n’est pas assez préparé, le candidat risque de se retrouver dans ce genre de situation déstabilisante.

Dom

Bon je reviens, avec le même rôle que tout à l’heure.
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.

Bouzar

Bonjour,
Tu trouveras dans ce livre des exemples :

Fin de partie

Parmi les exercices proposés par ce bouquin il y a:

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$.

Fin de partie

Un exercice difficile à faire en temps limité probablement:
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$.

Fin de partie

On peut aussi présenter des cas particuliers du théorème de la progression arithmétique de Dirichlet.
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)

Fin de partie

Le bouquin ci-dessus m'a l'air de s'inspirer d'un autre bouquin (pour l'agrégation externe mais le thème des nombres premiers y est aussi traité):

Agrégation mathématique, épreuve orale , 68 thèmes pour se préparer efficacement, Ivan Nourdin, Dunod.

chanig

Bonjour,

si j'ai bien compris, on peut mettre quand même des exercices qui dans l'énoncé , nous parle de "nombres premiers" (mais pas des exercices techniques d'entrainement sur les nombres premiers). Mais il faut aussi choisir un exercice qui dans sa résolution fait intervenir les nombres premiers ?

Les exos sont alors limités. Parce que la différence entre  "illustrant " et "faisant intervenir" est subtile quand même.

Z/pZ cyclique avec p premier, conviendrait quand même ?

Les nombres de Fermat ne conviennent pas ?

Merci.

Sato

J’ai cru comprendre qu’il faut éviter de déguiser un théorème en exercice. 

chanig

Le critère d'Eisenstein en exercice me parait pas mal non?

Rombaldi

Bonjour,

sur ce document, vous trouverez peut être des idées 

http://maths.rombaldi.free.fr/Livres/ErrataEtExercicesSupplementairesOral2.pdf

Bonne soirée

Sato

Merci !

Alacool

Sato a dit :

J’ai cru comprendre qu’il faut éviter de déguiser un théorème en exercice. 

Bonjour, il ne faut pas déguiser une leçon de cours en leçon d'exercices ! 

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.