[MPSI] Nombres premiers

Aide à la résolution d'exercices ou de problèmes de niveau Supérieur.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

[MPSI] Nombres premiers

Messagepar kahlane » Jeudi 04 Janvier 2007, 18:50

Bonjour, j'aimerais bien avoir un peu d'aide pour cette exercice, car je bloque un peu.

Soit $P(n)$ le nombre d'entiers premiers entre 2 et n.
soit Q(n) le n-iéme entier premier.

1) montrer que $ \forall  n \in \N, n \ge 2, \dfrac{2^{2n-1}}{n}< \begin{pmatrix} 
  2n  \\ 
  n 
  \end{pmatrix} <2^{2n-1} $( ça, je l'ai fait)

2) a) montrer que $ \forall  n \in \N, n \ge 2, \begin{pmatrix} 
  2n  \\ 
  n 
  \end{pmatrix}>{P(2n)-P(n)}$ (ça aussi je l'ai fait)

2) b) soit $p$, premier.
montrer que la valuation $v_p(n!)=  \ds\sum_{k=1}^{max(n!)}{E(\dfrac{n}{p^k})}$$max(n!)=E(\dfrac{ln(n)}{ln(p)})$
indication : on comptera parmis les entiers j de [1,n] ceux qui sont divisibles par $p^k$ sans etre divisibles par $p^{k+1}$, $1 \le k \le max(n!)$

là je ne voisq pas comment faire, meme en ce qui concerne l'indication...déjà je ner vois pas à quoi correspond $max(n!)$.
les entiers divisibles par $p^k$ s'écrivent sous la forme $k' \times p^k$, mais après....?

merci d'avance de bien vouloir m'aider
kahlane
Déca-utilisateur
 
Messages: 23
Inscription: Jeudi 28 Décembre 2006, 19:10

Publicité

Messagepar kilébo » Jeudi 04 Janvier 2007, 19:18

$max(n!)$ correspond au nombre où il est "inutile d'aller plus".

Ici tu divises pour mieux régner : tu cherches à regarder (cf. l'indication) dans l'ensemble $1, \cdots, n$ (et non pas dans $1, \cdots, n!$). Or pour que $p^k | n$ au minimum, si $n \neq 0$, c'est que $p^k \leq n$ qui se résoud en passant par le logarithme d'où le $mac(n!)$.

Regarde pour la suite et dis-nous si tu bloques encore.
A une erreur de calcul et de raisonnement prêt, tout cela doit être correct.
kilébo
Téra-utilisateur
 
Messages: 1059
Inscription: Samedi 22 Avril 2006, 11:08
Localisation: Région Parisienne
Statut actuel: Actif et salarié

Messagepar kahlane » Jeudi 04 Janvier 2007, 19:31

ok, j'ai compris le coup du $max(n!)$, merci, c'est logique : $p^k \le n \Leftrightarrow k \le \dfrac {ln(n)}{ln(p)}$, d'où $1 \le k\le E(\dfrac {ln(n)}{ln(p)})$, mais pourquoi ( et comment montrer ) l'égalité avec la valuation? et comment compter le nombre d'entiers divisibles par $p^k$mais pas par $p^{k+1}$?
kahlane
Déca-utilisateur
 
Messages: 23
Inscription: Jeudi 28 Décembre 2006, 19:10

Messagepar kilébo » Jeudi 04 Janvier 2007, 21:10

Pourquoi ne pas prendre un exemple et partons à la peche ! Car cela me paraît pas simple sinon. (C'est toujours ce qu'il faut faire en Math : regarder sur un exemple puis prendre le matériel de pêche !).

Prenons donc $n=37$, $p=3$ et $k=2$.

Alors $9 = 3^2$, $18 = 2.3^2$ et $36 = 4.3^2$ conviennent mais pas $27 = 3^3$.

On voit alors que $E(\dfrac{37}{3^2})$ représente le nombre d'éléments divisible par $3^2$, i.e. s'écrivant $q.3^2$, dans $1, \cdots, 37$ et $E(\dfrac{37}{3^3})$ le nombre d'éléments divisibles par $3^3$.

Déduis-en le nombre d'éléments recherchés dans l'indication dans le cas général.

Ensuite comment en déduire la valuation maintenant ?
A une erreur de calcul et de raisonnement prêt, tout cela doit être correct.
kilébo
Téra-utilisateur
 
Messages: 1059
Inscription: Samedi 22 Avril 2006, 11:08
Localisation: Région Parisienne
Statut actuel: Actif et salarié

Messagepar kahlane » Vendredi 05 Janvier 2007, 11:24

sur l'exemple, on c'est clair : le nombres d'entiers divisibles par $3^2$ mais pas par $3^3$ c'est $E(\dfrac{37}{3^2})-E(\dfrac{37}{3^3})$
mais dans le cas général est ce que c'est $E(\dfrac{n}{p^k})-E(\dfrac{n}{p^{k+1}})$? et si oui peut-on le dire comme ça, ou faut-il le montrer, parce que avec l'exemple c'est clair, mais sans on se demande d'où ça sort!!!
kahlane
Déca-utilisateur
 
Messages: 23
Inscription: Jeudi 28 Décembre 2006, 19:10

Messagepar Tryphon » Vendredi 05 Janvier 2007, 12:42

Combien y'a-t-il d'entiers divisible par $p^k$ ? Combien y'en-a-t-il divisibles par $p^{k+1}$ ? Combien y'en-a-t-il divisibles par $p^k$ mais pas par $p^{k+1}$ ?

Ca ressemble au début d'une démonstration du théorème de Bertrand (il existe un nombre premier entre $n$ et $2n$) ton truc non ?
Tryphon
Péta-utilisateur
 
Messages: 1840
Inscription: Mercredi 01 Juin 2005, 17:39
Localisation: Un peu plus à l'Ouest
Statut actuel: Actif et salarié | Enseignant

Messagepar kahlane » Vendredi 05 Janvier 2007, 13:56

et bien, il y a $E(\dfrac{n}{p^k})$ entiers divisibles par $p^k$, et $E(\dfrac{n}{p^{k+1}})$ entiers divisibles par $p^{k+1}$, donc $E(\dfrac{n}{p^k})-E(\dfrac{n}{p^{k+1}})$ entiers divisibles par $p^k$ mais pas par $p^{k+1^}$, mais ça je l'ai trouvé par analogie avec l'exemple, ça ne suffit pas à le prouver..?

et je ne connais pas le théorème de bertrand
kahlane
Déca-utilisateur
 
Messages: 23
Inscription: Jeudi 28 Décembre 2006, 19:10

Messagepar kilébo » Vendredi 05 Janvier 2007, 14:59

$E(\dfrac{n}{p^k})-E(\dfrac{n}{p^{k+1}})$ se démontre en écrivant les entiers $j$ divisibles par $p^k$ sous la forme $j = j'.p^k$$j'$ varie de 1 à $E(n/p^k)$.

Pour la suite, par quel nombre faut-il mulitplier $E(\dfrac{n}{p^k})-E(\dfrac{n}{p^{k+1}})$ pour obtenir la valuation un nombre $n$ s'il ne contenait que des éléments divisibles par $p^k$ et aucun par $p^{k+1}$ ?
A une erreur de calcul et de raisonnement prêt, tout cela doit être correct.
kilébo
Téra-utilisateur
 
Messages: 1059
Inscription: Samedi 22 Avril 2006, 11:08
Localisation: Région Parisienne
Statut actuel: Actif et salarié

Messagepar kahlane » Dimanche 07 Janvier 2007, 16:33

désolé de ne pas avoir répondu plus tot, je n'avais pas accès à internet.
merci pour la démo de l'indication, j'ai bien compris.

mais je ne suis pas sure de comment continuer, même avec ce que vous m'avez dit :
kilébo a écrit:Pour la suite, par quel nombre faut-il mulitplier $E(\dfrac{n}{p^k})-E(\dfrac{n}{p^{k+1}})$ pour obtenir la valuation un nombre $n$ s'il ne contenait que des éléments divisibles par $p^k$ et aucun par $p^{k+1}$ ?

nous on cherche la valuation de n! pas de n.

sinon on peut dire que si $n!$ ne contient que des éléments divisibles par $p^k$ et aucun par $p^{k+1}$, alors $n!=p^k.j'_1.p^k.j'_2....p^k.j'_n$, contenant n fois le terme $p^k$, et où $j'_i$ n'est pas divisible par $p^{k+1}$.
alors la valuation de p dans n! est $v_p(n!)=n.k$

donc dans notre cas, il faudrait multiplier $E(\dfrac{n}{p^k})-E(\dfrac{n}{p^{k+1}})$ par k? mais on obtient pas le résultat recherché...
kahlane
Déca-utilisateur
 
Messages: 23
Inscription: Jeudi 28 Décembre 2006, 19:10

Messagepar kilébo » Dimanche 07 Janvier 2007, 21:23

Si justement ! En multipliant par $k$ et en additionnant pour $k =1$ à $max(n!)$, on obtient le résultat.
A une erreur de calcul et de raisonnement prêt, tout cela doit être correct.
kilébo
Téra-utilisateur
 
Messages: 1059
Inscription: Samedi 22 Avril 2006, 11:08
Localisation: Région Parisienne
Statut actuel: Actif et salarié

Messagepar kahlane » Jeudi 11 Janvier 2007, 20:52

merci beaucoup de votre aide, et désolé de ne pas avoir répondu plus tot, je n'était pazs chez moi. maintenant j'ai rendu mon devoir. encore merci;
kahlane
Déca-utilisateur
 
Messages: 23
Inscription: Jeudi 28 Décembre 2006, 19:10


Retourner vers Exercices et problèmes : Supérieur

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Bing [Bot] et 6 invités