Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
164 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

L305, exercices illustrant emploi nb premiers

Envoyé par stephane_idf 
L305, exercices illustrant emploi nb premiers
il y a quatre mois
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



Edité 2 fois. La dernière correction date de il y a quatre mois et a été effectuée par AD.
Dom
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par AD.
Dom
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
Quel concours ?
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
c'est l'agreg interne leçon 305
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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).
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
Caractérisation des nombres premiers: Théorème de Wilson.

[fr.wikipedia.org]

Variations autour du théorème de Wilson:
[www.idpoisson.fr]

Loi de réciprocité quadratique:
[www.math.u-psud.fr]

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.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
geo
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
Fonction d'Euler
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
Geo:
La fonction d'Euler est définie sur $\mathbb{N}$ privé de $0$.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
xax
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
La construction des nombres p-adiques
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
@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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
Il y a aussi le critère d'Eisenstein:
[fr.wikipedia.org]

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
Citation
parisse
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 ?

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par nicolas.patrois.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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. grinning smiley
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.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par nicolas.patrois.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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?

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Fin de partie.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
Un autre exemple de chiffrement:

[fr.wikipedia.org]

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.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Fin de partie.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
Comment chiffrer avec une courbe ? Par leur entremise...

f(n) = 2 + (2(n!) mod(n + 1)) où f(n) = n + 1 si n + 1 est dans P et f(n) = 2 sinon
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
@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
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par nicolas.patrois.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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…

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Dom
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
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.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
Bonjour,
Tu trouveras dans ce livre des exemples :


Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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$.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 4 fois. La dernière correction date de il y a quatre mois et a été effectuée par Fin de partie.
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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$.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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)

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: 305 Exercices illustrant l'emploi nb premiers
il y a quatre mois
avatar
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.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 136 310, Messages: 1 317 658, Utilisateurs: 24 007.
Notre dernier utilisateur inscrit liny195.


Ce forum
Discussions: 4 253, Messages: 79 697.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page