Agrégation interne 2023 partie I valuations p-adiques — Les-mathematiques.net The most powerful custom community solution in the world

Agrégation interne 2023 partie I valuations p-adiques

Modifié (February 2023) dans Algèbre
Bonsoir
Ayant traité cette série de questions très rapidement (35 min), je me demande si je n'ai pas d'erreurs, avant de m'attaquer à la fameuse formule de Legendre. 

7) Soit $n \in \Z^{*}$ et $p$ un nombre premier. 
L'ensemble $A=\{ k \in \N \ | \ p^k \mid n \}$ est non vide (il contient $0$) et majoré par $|n|$. En effet, pour tout entier $k \in \N$ tel que $k \mid n$, on a $k \leq p^k \leq |n|$. 
L'ensemble $A$ est non vide et majorée, il possède donc un plus grand élément.

8) Commençons par montrer le lemme suivant : $\boxed{v_p(n)= k \iff \exists q \in \Z ,\   \ q \wedge p=1 \ \ , n=p^k q }$.
  • Si $k=v_p(n)$ alors $p^k \mid n$. Écrivons $n=p^k q$, alors $p$ ne divise pas $q$ puisque $p^{k+1}$ ne divise pas $n$, donc $p \wedge q=1$ car $p$ est premier.
  • Réciproquement, supposons que $n=p^k q$ où $p \wedge q=1$, alors $n$ est divisible par $p^k$ mais pas par $p^{k+1}$ car $p$ ne divise pas $q$.
Le lemme permet d'écrire que $a=p^{v_p(a)}q$ et $b=p^{v_p(b)} q'$ avec $q \wedge p= q' \wedge p=1$ et $q,q' \in \Z$.
Alors $ab= p^{v_p(a)+v_p(b)} (qq')$ avec $qq' \wedge p=1$. 
Le lemme permet de conclure $\boxed{\forall (a,b) \in \Z^2, \ v_p(ab)=v_p(a) v_p(b)}$.

9) Si $a/b=c/d$ alors $ad=bc$. Donc $v_p(ad)=v_p(bc)$.
La question 8 donne immédiatement $v_p(a)+v_p(d)=v_p(b)+v_p(c)$. 
Finalement : $\boxed{v_p(a)-v_p(b)= v_p(c)-v_p(d)}$.

10) Posons $r=a/b$ et $s=a'/b'$ avec $a,a',b,b' \in \Z^{*}$.
On a $rs= \dfrac{aa'}{bb'} \in \Q^{*}$.
Donc $v_p(rs)=v_p( aa') - v_p(bb') =v_p(a)+v_p(a')-v_p(b) - v_p(b')$.
Ainsi $v_p(rs)=v_p(a)-v_p(b) + v_p(a') -v_p(b')$.
Enfin $\boxed{v_p(rs)=v_p(r)+v_p(s)}$.

11) Posons $r=p^{v_p(r)} q$ et $s=p^{v_p(s)} q'$ avec $q,q' \in \Z$ et $q \wedge p=q' \wedge p=1$.
Deux cas se présentent : 
  • Si $v_p(s) \geq v_p(r)$. On a $r-s=p^{v_p(r)} (q- q' p^{v_p(s)-v_p(r)})$ donc $p^{v_p(r)} \mid r-s$. Ainsi $v_p(r-s) \geq v_p(r)= \min (v_p(r),v_p(s))$.
  • Si $v_p(r) \geq v_p(s)$. On a $r-s=p^{v_p(s)} (p^{v_p(r)v_p(s)} q- q')$ donc $p^{v_p(s)} \mid r-s$. Ainsi $v_p(r-s) \geq v_p(s)= \min (v_p(r),v_p(s))$.
On a montré que $\boxed{v_p(r-s) \geq \min (v_p(r),v_p(s))}$.

12) $v_p(0)=+ \infty$.
Pour la 10 : 
Si $r=s=0$ alors $v_p(rs)=v_p(0)=+ \infty$ et $v_p(r)+v_p(s)=v_p(0)+v_p(0)=+ \infty + \infty = + \infty$
Si $r=0$ et $s \ne 0$  alors $rs=0$ et $v_p(rs)=+ \infty$ et $v_p(r)+v_p(s)=v_p(0)+v_p(s)=+ \infty$
Si $r \ne 0$ et $s=0$ c'est le même raisonnement par symétrie.

Pour la 11 : 
Si $r=0$ alors $v_p(r-s)=v_p(-s)=v_p(s)$ et $\min (v_p(0),v_p(s))=\min (+ \infty,v_p(s))=v_p (s)$
Si $s=0$, alors $v_p(r-s)=v_p(r)$ et $\min (v_p(r),v_p(0))=\min (v_p(r),+ \infty)=v_p (r)$


Mots clés:
«1

Réponses

  • Modifié (February 2023)
    Je continue, le niveau s'élève un peu. Est-il utile d'exhiber une bijection pour le dénombrement de $E_k$ ? Ou on peut faire plus vite ? 

    13) $E_k= \{ i \in [|1,n |] \ | \ v_p(i) \geq k \}$. Les $E_k$ sont les multiples de $p^k$.
    $E_k= \{ i \in [|1,n |] \ | \ p^k \ \text{divise} \ i \} =\{ p^k q \ | q \in \N \ |  \ 1 \leq p^k q \leq n \}$
    Donc $E_k = \{ p^k q \ | \ q \in \N \cap [1 , n/p^k ] \}$
    Soit $\boxed{E_k = \{ p^k q \ | \ q \in [|1, \lfloor n/p^k \rfloor |] }$.

    L'application $\phi : p \mapsto p^k q$ induit une surjection de $[|1, \lfloor n/p^k \rfloor |]$ sur $E_k$. Elle est trivialement injective.

    On en déduit que : $\boxed{\# E_k =\lfloor n/p^k \rfloor  }$.












  • Modifié (February 2023)
    Salut OS
    Ta rédaction du 7) me laisse un peu perplexe. L'idée de l'ensemble $A$ me semble bonne, par contre le fait que $|n|$ majore tous les éléments de $A$ me paraît bizarre.
    J'aurais plutôt justifié le fait qu'il existe un unique entier naturel $k_1$ tel que $p^{k_1}\leq n<p^{k_1+1}$ en utilisant que $[0;+\infty[ = \bigcup\limits_{k=0}^\infty [p^k; p^{k+1}[$. 
    Une décomposition de $|n| >1$ en premier de facteurs premiers donne le résultat à cause de l'unicité de la décomposition.
    Jean-éric
  • Bonjour,

    Tiens, c'est rigolo, j'ai posé la question 15 en exercice il y a quelques années en TS.

    Cordialement,
    Rescassol

  • Modifié (February 2023)
    @jean-éric
    Je ne comprends pas ta preuve, à aucun moment tu ne prends un élément de l'ensemble $A$. Je ne vois pas où tu montres le résultat. Tu donnes deux résultats non démontrées que je ne possède pas dans mes cours. 
    De plus, ça me semble bien compliqué, alors qu'il y a très simple, niveau terminale. 
    Soit $k \in \N$ tel que $p^k$ divise $n$ donc divise $|n|$. Ainsi $k \in A$.  Alors $\boxed{p^k \leq | n |}$.
    Montrons par récurrence que $\forall k \in \N \ k \leq p^k$. On a $0 \leq p^0=1$. Si la propriété est vraie au rang $k \geq 1$, alors $p^{k+1} =k p^k  \geq k p \geq 2 k $ car $p \geq 2$. Mais $2k \geq k+1$ car $k \geq 1$. Donc $p^{k+1} \geq k+1$ ce qui prouve le résultat par récurrence sur $k$.
    On a montré que $\boxed{k \in A \ \implies k \leq p^k \leq |n| }$. Ainsi, $A$ est une partie majorée par $|n|$.


    @Rescassol
    J'aime bien la question $15$  B) 

  • Dans la question 7, tu oublies de préciser que ton ensemble $A$ est une partie de $\N$, ce qui est primordial.

    Pour ce qui est du cardinal de $E_k$, tu peux utiliser la définition de la division euclidienne pour conclure sans bijection.
  • Pour $k \leq p^k$, il y a une erreur dans ta preuve : ($p^{k+1}=k p^k$). D'ailleurs puisque $p\geq 2$, tu peux te contenter de montrer que $k \leq 2^k$.
  • Pour la 7), on peut utiliser aussi la décomposition en facteurs premiers des entiers.
  • Modifié (February 2023)
    @Julia Paule
    Ok merci. On a $2^0=1 \geq 0$. Si $P_k$ est vraie pour $k \geq 1$, on a $2^{k+1}=2 \times 2^k \geq 2k \geq k+1$.

    @bisam
    Oui merci.
    Je n'ai pas compris comment utiliser la définition de la division euclidienne pour déterminer le cardinal de $E_k$.





  • Modifié (February 2023)
    Re OS
    Je n'avais pas vu cela comme çà avec une récurrence. 
    Sincèrement dès que $p^k\leq |n|$, on a $k\leq \frac{\ln |n|}{\ln p}$ ($\ln p>0$ car $p\geq 2$), et donc $k \leq E\left( \frac{\ln |n|}{\ln p}\right)+1$ ce qui me semble plus simple.
    Bonne soirée OS.
  • Modifié (February 2023)
    C'est en effet un très bon moyen de progresser : 




    Pour rappel "sa résolution" : https://les-mathematiques.net/vanilla/index.php?p=/discussion/2333248/agregation-interne-2023-partie-i-valuations-p-adiques



    Je continue ?

  • Givré ce Oshine
  • @Xavier Var
    Oui et alors ? C'est du cours que je connais par cœur. J'ai étudié ce livre durant deux ans. 
    Ou alors je dois réinventer le cours par moi-même ? 

    Pour la 7 @Julia Paule, si $n=1$, alors $A$ est majoré par $1$. En effet, $p$ ne divise pas $1$.
    Si $n \geq 2$ alors $n$ admet une unique décomposition en facteurs premiers $n=p_1 ^{\alpha_1} \cdots p_r ^{ \alpha_r}$. Si $k \in A $ alors $p^k$ divise $n$ donc $\exists i \in [|1,r|]$ tel que $k \leq  \alpha_i$. 
    $A$ est majorée par $\max (\alpha_1, \cdots, \alpha_r)$, c'est une partie non vide et majorée, elle admet un plus grand élément.

    14) J'ai l'impression que l'énoncé complique inutilement la preuve, je sais démontrer la formule de Legendre mais je ne comprends pas leur histoire du nombre d'entiers $k$ tel que $ i \in E_k$, et pour moi ça ne sert à rien dans la démonstration...

    $E_k = \{ j \in [|1,n|] \ | \ v_p(j) \geq k \}$. On cherche le nombre d'entiers $k$ tels que $v_p(i) \geq k$.

    $\# E_k=0$ si $p^k > n$ soit $k > \ln (n) / \ln (p)$

    Je ne sais pas si c'est ce qui est demandé je ne comprends pas la méthode donnée par le sujet pour démontrer la formule de Legendre.




  • Non tu l'as recopié, on arrête le mensonge. Ne nous fais pas croire que tu aurais exactement fait ça le jour de l'agrégation. Quelle mauvaise foi ! 
    Ton comportement (le fait de recopier) montre clairement un manque terrible de reconnaissance.
  • @Xavier Var : Entièrement d'accord. J'ajouterai que c'est un manque de respect pour ceux qui passent ou ont passé vraiment le concours.
  • Modifié (February 2023)
    Bonjour
    Encore pris la main dans le sac ! 
     
  • Modifié (February 2023)
    @Xavier Var
    Au moins j'ai reconnu direct un  passage de cours que j'avais étudié.
    La première fois que j'ai étudié les valuations ça me semblait compliqué, maintenant ça me semble facile. 

    Par contre la 14 utilise une méthode différente de celle du Liret, donc je ne peux pas trop recopier.
  • Pour la 14 je suis bloqué je ne comprends pas la première partie de la question.
  • Modifié (February 2023)
    Je ne suis pas d'accord @Xavier Var : il faut louer l'effort de rédaction qu'a fait Oshine en changeant quelques mots de liaisons :D 
    C'est plus que ridicule, surtout quand on a plus de 25 ans(je suppose)...

    @OShine, oui tu dois "réinventer le cours", comme le firent les candidats à l'agrégation interne il y a une semaine environ ! Si tu n'as pas envie de refaire ces questions, tu fais les autres et basta, mais recopier le cours pour répondre sur un forum... Bref.
  • @OS, commence par t'inscrire l'année prochaine, après tu nous feras un topo de ce que tu as produit à l'écrit car ce que tu fais là n'a pas d'intérêt, ni pour toi, ni pour ceux qui te lisent (saintes personnes).
    Les solutions dans tes bouquins ne correspondent pas à l'épreuve : c'est au candidat de s'adapter au sujet (et en conditions, ie tu as 6h, avec le stress et tout et tout), certaines questions te rappellerons des résultats que tu connais, voire même que tu sais démontrer, mais pas forcément comme le sujet entend te le faire prouver... C'est à toi de t'adapter.
  • C'est pas vrai :(  !!!! J'ai répondu super à du cours. Cela explique l'hétérogénéité des réponses de OS. Bon, je vais arrêter de perdre mon temps. Merci @Xavier Var ! Stp, de quel livre est tiré ce recopiage ?
  • Modifié (February 2023)
    Ca a l'air d'être du tout en un DUNOD MPSI. En tout cas, bien (bien) plus que d'être irrespectueux envers les candidats, c'est surtout irrespectueux envers ceux qui prennent le temps de te répondre.
  • Modifié (February 2023)
    La question 14 n'est pas dans les livres.
    On dirait que la méthode est différente.
    Je ne comprends pas la première partie de la question.
    À partir de la question 16 je n'ai jamais vu ces résultats dans un cours.
  • Modifié (February 2023)
    La question 14 est tellement classique que tu as dû la traiter quand tu étais en sup... Elle est très probablement dans les exercices corrigés également.
    Mais surtout, elle ne fait que reprendre les résultats démontrés précédemment, en y ajoutant une étape de calcul ultra classique.
    La question 15 est une application du résultat précédent.
    Enfin, la 16 est une majoration triviale.
    Je comprends l'énervement de tous ceux qui t'ont répondu jusqu'ici dans ce fil.
    Tu viens en te targuant d'avoir réussi certaines questions et en voulant une approbation alors que tu sais pertinemment que c'est juste puisque tu as recopié un cours. Ensuite tu te plains de ne pas savoir faire la suite, ou plus exactement de ne jamais l'avoir vue résolue quelque part (ce qui t'empêche sans doute de nous éblouir par ton talent à la recopier ?)
    Bref, bien que je trouve ce sujet intéressant, je vais te laisser te débrouiller car tu as encore dépassé les bornes.
  • @bisam
    Désolé...
    Mais 9-10-12 ne sont pas traitées dans le tout en un mpsi je les ai faites moi-même.
    Je sais faire la 14 mais pas en suivant leur indication qui m'embrouille. Je ne comprends pas leur méthode.
    Les 15 et 16 je sais faire je pense.
  • Modifié (February 2023)
    Dans le tout en un $n$ est un entier naturel et ici il est relatif donc ce n'est pas exactement pareil.
  • Modifié (February 2023)
    @pozzar
    Tu as raison. 
    La démonstration du Liret n'a rien à voir avec celle-ci pour la $14$, elle semble plus facile et plus naturelle, le concepteur du sujet complique inutilement les choses en mettant une démonstration technique avec des doubles indices et des ensembles difficiles à manipuler. 

    14) On a $i \in E_k \iff v_p(i) \geq k$. Donc $\boxed{\# \{k \in \N^{*} \ | \ i \in E_k \} = v_p(i)}$. 
    On a $v_p(n!)=v_p(1 \times 2 \times \cdots \times n)= \displaystyle\sum_{i=1}^n v_p (i)=\displaystyle\sum_{i=1}^n \# \{k \in \N^{*} \ | \ i \in E_k \}  $. 
    Je bloque ici. J'admets que je ne sais pas faire cette question avec la méthode de ce sujet. 

    15) $v_2(100!)= \displaystyle\sum_{k=1}^{+\infty} \lfloor \dfrac{100}{2^k} \rfloor= \lfloor \dfrac{100}{2} \rfloor +  \lfloor \dfrac{100}{4} \rfloor +  \lfloor \dfrac{100}{8} \rfloor +  \lfloor \dfrac{100}{16} \rfloor+  \lfloor \dfrac{100}{32} \rfloor+  \lfloor \dfrac{100}{64} \rfloor+ 0$
    Donc $v_2(100!)= 50 + 25+12+6+3+1$ d'où $v_2(100!)=97$
    De plus, $v_5(100!)= \displaystyle\sum_{k=1}^{+\infty} \lfloor \dfrac{100}{5^k} \rfloor= \lfloor \dfrac{100}{5} \rfloor +  \lfloor \dfrac{100}{25} \rfloor + 0$
    Donc $v_5(100!)=20+4=24$
    Finalement, le nombre de $0$ de $100!$ est $\min (v_2(100!),v_5(100!))=\min(24,97)=24$

    16) Soit $n \in \N^{*}$.
    On sait que $\forall k \ \  \lfloor \dfrac{n}{p^k} \rfloor \leq \dfrac{n}{p^k} $. Donc $v_p(n!) \leq \displaystyle\sum_{k=1}^{+\infty}  \dfrac{n}{p^k}  $
    Mais $\displaystyle\sum_{k=1}^{+\infty}  \dfrac{n}{p^k} =\dfrac{n}{p}  \displaystyle\sum_{k=0}^{+\infty}  (\dfrac{1}{p})^k =\dfrac{n}{p} \dfrac{1}{1-1/p}  $. Donc  $\displaystyle\sum_{k=1}^{+\infty}  \dfrac{n}{p^k} =\dfrac{n}{p-1}$
    On a montré $\boxed{\forall n \in \N^{*} \ v_p(n!) \leq \dfrac{n}{p-1}}$
  • Finalement c'est bon.
    On note $\mathcal P(i,k)$ la propriété $i \in E_k$ .
    On a $\{ (i,k) \in [|1,n|] \times \N^{*} \ | \ \mathcal P(i,k) \} = \displaystyle\bigcup_{i \in [|1,n |]} \{ k \in \N^{*} | \ \mathcal P(i,k) \} = \displaystyle\bigcup_{k \in \N^{*}} \{ i \in [|1,n|] | \ \mathcal P(i,k) \} $
    $v_p(n!)=\displaystyle\sum_{i=1}^n \# \{k \in \N^{*} \ | \ i \in E_k \} = \displaystyle\sum_{k \in \N^{*}}  \# \{i \in [|1,n|] \ | \ i \in E_k \}    $. 
    D'où $v_p(n!)= \displaystyle\sum_{k \in \N^{*}}  \# E_k$. 

    Mais d'après la question précédente, $ \# E_k= \lfloor \dfrac{n}{p^k} \rfloor$ .
    Enfin : $\boxed{v_p(n!)= \displaystyle\sum_{k=1}^{+\infty}  \lfloor \dfrac{n}{p^k} \rfloor}$.
  • Je bloque sur la 17 comme prévu. 

    17) J'ai d'abord essayé un calcul explicite mais je n'ai pas abouti. Pour la récurrence, je ne trouve pas l'idée pour utiliser l'hypothèse de récurrence.

    Soit $k \in \N^{*}$. $k$ se décompose de manière unique en la somme $k=\displaystyle\sum_{i=0}^q u_i 2^i$ où $q \in \N$, $(u_0, \cdots, u_q) \in \{0,1\}^{q+1}$ et $u_q \ne 0$.
    Ainsi $\boxed{k+1=(u_0 +1)2^0 + \displaystyle\sum_{i=1}^q u_i 2^i}$

    Montrons le résultat par récurrence sur $k$.
    • Si $k=1 \times 2^0$, on a $v_2(1+1)=v_2(2)=1$ et $s(1)-s(2)+1=1-1+1=1$ donc le résultat est vraie au rang $k=1$.
    • Supposons $\mathcal P_k$ vraie.








  • Merci @Barry. Je vérifierai quand je rentrerai chez moi.
  • Pour la $17$, je vais tester sur des petits nombres.

    Si $k=7=1 \times 2^0+1 \times 2 + 1 \times 2^2$. On a $k+1=8=1 \times 2^3$.
    $v_2(k+1)=v_2(8)=3$. Et $s(k)=s(7)=3$, $s(k+1)=s(8)=1$ donc $s(k)-s(k+1)-1=3-1+1=3$.

    Commençons par traiter le cas $u_0=0$.

    On a alors $k=u_1 2 + u_2 2^2+ \cdots + u_q 2^q$. Soit $k+1=1 \times  2^0 + u_1 2 + u_2 2^2+ \cdots + u_q 2^q$
    Donc $k$ est pair et $k+1$ impair. Ainsi, $v_2(k+1)=0$.
    $s(k+1)=s(k)+1$. 
    Mais $s(k)-s(k+1)+1=-1+1=0$
    Le résultat est vérifié.

    Si $u_0 \ne 0$, ça me semble trop difficile, il y a trop de cas possibles.




  • Modifié (February 2023)
    17.
    Notons $m=v_{2}\left(k+1\right)$. Alors il existe $q$ naturel tel que $k+1=2^{m}\left(2q+1\right)$. L'écriture de $q$ en base $2$ donne donc l'existence d'une suite de bits $\left(u_{i}\right)_{i\in r}$ telle que $2q+1=2\left(\sum_{i\in r}u_{i}2^{i}\right)+1$. Donc $k+1=\sum_{i\in r}u_{i}2^{\overbrace{m+1+i}^{>m}}+1.2^{m}$ et donc $s\left(k+1\right)=1+\sum_{i\in r}u_{i}$. Mais\[k=2^{m}\left(2q+1\right)-1=2^{m+1}q+2^{m}-1=\sum_{i\in r}u_{i}2^{\overbrace{m+1+i}^{>m}}+\sum_{i\in m}1.2^{i}\] donc $s\left(k\right)=m+\sum_{i\in r}u_{i}$ donc $s\left(k\right)-s\left(k+1\right)=m-1$ ce que l'on voulait prouver.
    édit : coquille corrigée.
  • Pour tout $n\in\N^*$, $$s(2n)=s(n) \quad \text{et} \quad s(2n+1)=s(n)+1.$$
  • Modifié (February 2023)
    @Audeo
    Oui mais ce n'est pas ça qui m'a posé problème, c'est plutôt comment faire le lien avec la valuation 2-adique. 

    @troisqua
    Merci beaucoup pour ta réponse. 
    Mais il n'y a pas une coquille a la ligne $2$ ?
    $k+1=2^m  ( 2 \sum_{i \in r} u_i 2^i  +1 )= \boxed{  \sum_{i \in r} u_i 2^{m+i+1} + 2^m }$
    Tu as mis  $k+1=2^m  ( 2 \sum_{i \in r} u_i 2^i  +1 )=  \sum_{i \in r} u_i 2^{m+i+1} +1 \times 2^0$
    Tu as mis $2^0$ au lieu de $2^m$...
  • La coquille est bien là mais ne change rien à la somme des chiffres ni à la preuve. Je l'ai corrigée.
  • Modifié (February 2023)
    Ok merci mais c'est moi, je n'arrive pas avec les sommes écrites de la façon $\sum_{i \in r}$. Je ne sais pas ce que signifie $\sum_{i \in m}$. Il me semble aussi que le cas $q=0$ a été oublié car la décomposition n'est pas valable pour les entiers nuls.
    Je recopie la preuve en mettant des sommes que j'arrive à manipuler. Il me semble que traiter le cas $q=0$ permet de voir l'idée de la démonstration
     La décomposition unique n'étant possible que si $n$ est un entier naturel non nul.

    17) On a $m=v_2(k+1)$. Donc $2^m$ est le plus grand entier qui divise $k+1$. Ainsi, il existe $q \in \N$ tel que $k+1=2^m (2q+1)$. Si $q=0$ alors $ k+1=2^m$ et $s(k+1)=1$. On a $k=2^m-1=(2-1)(1+2+ \cdots +2^{m-1})$ Donc $s(k)=m$. On a $s(k)-s(k+1)+1=m-1 +1=m$.
    L'égalité est vérifiée. 
    Si $q \in \N^{*}$, il existe une unique décomposition en base 2 sous la forme $q= \displaystyle\sum_{i=0}^q u_i 2^i$. 
    Donc $2q+1= 2 \displaystyle\sum_{i=0}^q u_i 2^i +1$. Ainsi $\boxed{k+1=2^m + \displaystyle\sum_{i=0}^q u_i 2^{m+i+1}}$
    On a $k+1=1 \times 2^m + u_0 2^{m+1}+ u_1 2^{m+2 } + \cdots + u_{q} 2^{m+q+1}$
    Ainsi : $\boxed{s(k+1)=1+ \displaystyle\sum_{i=0}^q u_i}$ 
    De plus, $k=k+1- 1 = 2^m(2q+1)-1 = 2^m q + 2^m -1 = \displaystyle\sum_{i=0}^q u_i 2^{m+i+1}+2^m-1$
    Mais $2^m-1= (2-1) \displaystyle\sum_{i=0}^{m-1} 2^i$
    Ainsi $ \boxed{k=\displaystyle\sum_{i=0}^q u_i 2^{m+i+1} +  \displaystyle\sum_{i=0}^{m-1} 2^i}$
    Donc $s(k)= m +  \displaystyle\sum_{i=0}^q u_i$. Donc $s(k)-s(k+1)+1= m +  \displaystyle\sum_{i=0}^q u_i -1 -\sum_{i=0}^q u_i+1$
    Ce qui montre finalement : $\boxed{\forall k \in \N^{*}, \ v_2(k+1)=s(k)-s(k+1)+1}$.
  • OShine a dit :
    Pour la récurrence, je ne trouve pas l'idée pour utiliser l'hypothèse de récurrence.
    J'ai alors cru bien faire en postant cette proposition ; en effet, pour $k\in\N^*$, si $k+2$ est pair, alors $k+2=2t$ avec $t\in\llbracket2,k+1\rrbracket$ et : $$v_2(k+2)=v_2(t)+1, \quad s(k+1)=s(2t-1)=s(2(t-1)+1)=s(t-1)+1 \quad \text{et} \quad s(k+2)=s(t),$$ et si $k+2$ est impair, alors $k+2=2t+1$ avec $t\in\N^*$ et $$v_2(k+2)=0, \quad s(k+1)=s(t) \quad \text{et} \quad s(k+2)=s(t)+1.$$ 
  • Je n'ai pas "oublié" le cas $q=0$, je me suis juste intéressé aux cas non triviaux. Quant à l'écriture qui te chagrine, $0=\emptyset$ et si $n$ est naturel non nul alors $n=\{0;\dots;n-1\}$.
  • Modifié (February 2023)
    Ou bien soit $r$ le nombre de digits $1$ à droite de $k$ (avant le premier digit $0$). Alors $k=1+2+2^2+\cdots +2^{r-1}+\sum_{m=r+1}^i u_m 2^m$.
    On a $k+1=2^r+\sum_{m=r+1}^i u_m 2^m$ et $s(k)-s(k+1)+1=r-1+1=r=v_2(k+1)$.
  • @Julia Paule  : J'aime bien aussi ça :)
  • Modifié (February 2023)
    J'ai l'impression que ces questions pourraient être données au lycée, elles ne nécessitent pas de connaissances du supérieur. 

    @Audeo
    Joli !

    @Julia Paule
    Intéressant mais très astucieux. 

    Après pour moi la preuve la plus naturelle est intuitive est celle de @troisqua, même si elle nécessite quelques calculs. 
    Après la question $17$ qui demandait de la réflexion, la $18$ se fait très rapidement. 

    18) On a $v_2(n!)= \displaystyle\sum_{k=1}^n v_2(k)= v_2(1) + \sum_{k=2}^n v_2(k)$ avec $v_2(1)=0$.
    Le changement d'indice $j=k-1$ fournit $v_2(n!)=  \displaystyle\sum_{j=1}^{n-1} v_2(j+1)$.
    D'après la question précédente, comme $j \geq 1>0$, on a $\forall j \in [|1,n-1|] \ v_2(j+1)=s(j)-s(j+1)+1$.
    D'où : $v_2(n!)=n-1+ \displaystyle\sum_{j=1}^{n-1}  ( s(j)-s(j+1))$
    C'est une somme télescopique, ce qui donne $v_2(n!)=s(1)-s(n) +n-1$ avec $s(1)=1$.
    Finalement : $\boxed{v_2(n!)= n - s(n)}$. 
    Je vais tenter de trouver 19-20 sans demander d'aide.
  • Pour la 17., il n'y a pas beaucoup d'astuce dans ma preuve, c'est juste l'histoire de la retenue qui marche particulièrement bien quand les nombres sont écrits en base 2, où tous les digits passent de 1 à 0 sur la droite quand on ajoute 1 à un nombre, jusqu'au 1er 0 rencontré qui passe à 1.
  • Julia Paule a dit :
    Pour la 17., il n'y a pas beaucoup d'astuce dans ma preuve, c'est juste l'histoire de la retenue qui marche particulièrement bien quand les nombres sont écrits en base 2, où tous les digits passent de 1 à 0 sur la droite quand on ajoute 1 à un nombre, jusqu'au 1er 0 rencontré qui passe à 1.
    Ok merci, mais ça je n'avais pas cette intuition donc je n'aurais jamais trouvé avec ta méthode. 
    C'est l'utilisation de la formule $1+2+ \cdots +2^{n-1} = 2^n-1$ qui m'a permis de comprendre la logique. 
  • Modifié (February 2023)
    La $19$ me pose des difficultés, j'ai fait des choses mais je n'aboutis pas. 

    19) 
    Soit $n$ une puissance de $2$. Il existe $a \in \N^{*}$ tel que $n=2^{a}$.
    Soit $k \in [|1,n-1|]$. 
    On a : $ \displaystyle\binom{n}{k} = \dfrac{n!}{ k! (n-k)!}$.
    On a $v_2( n!)=n- s(n)=2^a - s(2^a)$. On a montré : $\boxed{v_2(n!)=2^a-1}$.
    De plus, $v_2( k! (n-k)!) = v_2(k!) + v_2 ( (n-k)!) = k -s(k)+ n-k - s(n-k)$
    Donc $\boxed{v_2( k! (n-k)!) =2^a- s(k) -s (n-k)}$.
    On a : $v_2(  \displaystyle\binom{n}{k}  ) =v_2(n! )-v_2( k! (n-k)!) $
    Donc $v_2(  \displaystyle\binom{n}{k}  ) =2^a-1 - ( 2^a -s(k)-s(n-k) )= \boxed{-1 -s (k) -s(2^a -k)}$
    On doit maintenant exprimer $s(2^a-k)$ en fonction de $s(k)$.
    Comme $k \in \N^{*}$, on peut écrire $k= \displaystyle\sum_{i=0}^{q} u_i 2^i$ où $q<a$ car $k<n$.
    Donc $2^a-k=$ je m'arrête ici le $-k$ me gêne dans l'énoncé la décomposition est donnée pour des entiers strictement positifs.
  • Modifié (February 2023)
    OShine a dit :
    Donc $v_2(  \displaystyle\binom{n}{k}  ) =2^a-1 - ( 2^a -s(k)-s(n-k) )= \boxed{-1 -s (k) -s(2^a -k)}$
    La deuxième égalité est fausse, on trouve plutôt : $-1+s(k)+s(n-k)$, ce qui conclut permet immédiatement de conclure.  Pourquoi ? 
  • Modifié (February 2023)
    Oui merci j'ai fait une erreur de calcul niveau collège, la fatigue... Ces questions nécessitent beaucoup de réflexion pour moi. 
    On a $\boxed{v_2 (\binom{n}{k})= -1 + s(k) + s(n-k)}$.
    Comme $k>0$, alors $s(k) \geq 1$. De plus, $1 \leq k \leq n-1 \iff 1 \leq n-k \leq n-1$.
     Donc $n-k >0$ et $s(n-k) \geq 1$.
    D'où $v_2  (\binom{n}{k})  \geq -1 +1+1$ et enfin : $\boxed{v_2 ( (\binom{n}{k})) \geq 1}$ ce qui montre que $2$ divise $\binom{n}{k}$. 
  • Modifié (February 2023)
    20) Je ne trouve pas l'idée pour cette question, j'ai tout essayé.
    N'ayant pas réussi le sens direct j'ai tenté la contraposée.
    Supposons que $n$ ne soit pas une puissance de $2$. Alors il existe un facteur premier $q$ différent de $2$ tel que $q \mid n$. On a $v_q(n) >0$.
    Montrons qu'il existe $k \in [|1,n-1|]$ tel que $\binom{n}{k}$ ne soit pas pair. Mais ici je ne vois pas comment avancer.
  • Si $m$ et $k$ sont des entiers naturels tels que $k$ est impair et au moins égal à $3$, alors $v_2(\binom{2^mk}{2^m})=\dots$
  • @Audeo, pas mal pour la 17 !
  • Modifié (February 2023)
    Pour la 20, par contraposée, si $n$ n'est pas une puissance de $2$, alors il existe $m$ dans l'écriture binaire de $n$ tel que $2^m<n$ et $u_m=1$. Alors $s(n-2^m)=s(n)-1$. On obtient que la valuation 2-adique du coefficient binomial $v_2(\binom{n } { 2^m})=-s(n)+s(2^m)+s(n-2^m)=0$, donc que ce coefficient est impair.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!